This thesis addresses the problem of approximating analytic functions over general and compact multidimensional domains. Although the methods we explore can be used in complex domains, most of the tests are performed on the interval $[-1,1]$ and the square $[-1,1]\times[-1,1]$. Using Fourier and polynomial frame approximations on an extended domain, well-conditioned methods can be formulated. In particular, these methods provide exponential decay of the error down to a finite but user-controlled tolerance $\epsilon>0$. Additionally, this thesis explores two implementations of the frame approximation: a singular value decomposition (SVD)-regularized least-squares fit as described by Adcock and Shadrin in 2022, and a column and row selection method that leverages QR factorizations to reduce the data needed in the approximation. Moreover, strategies to reduce the complexity of the approximation problem by exploiting randomized linear algebra in low-rank algorithms are also explored, including the AZ algorithm described by Coppe and Huybrechs in 2020.

This thesis project focuses on algorithms that generate good sampling points for function approximation. In one dimension, polynomial interpolation using equispaced points is unstable, with high Oscillations near the endpoints of the interpolated interval. On the other hand, Chebyshev nodes provide both stable and highly accurate points for polynomial interpolation. In higher dimensions, optimal sampling points are unknown. This project addresses this problem by finding algorithms that are robust in various domains for polynomial interpolation and least-squares. To measure the quality of the nodes produced by said algorithms, the Lebesgue constant will be used. In the algorithms, a number of numerical techniques will be used, such as the Gram-Schmidt process and the pivoted-QR process. In addition, concepts such as node density and greedy algorithms will be explored.