## 1 Introduction
A fourth advantage is that the \(i\)th element of \(p_{K}(\mathbf{A})\mathbf{b}\) only depends on the elements of \(\mathbf{b}\) within \(K\) hops of \(i\) on the graph associated with \(\mathbf{A}\) (e.g., if \(\mathbf{A}\) is a graph Laplacian matrix, a nonzero entry in the \((i,j)\)th element of \(\mathbf{A}\), where \(i\
eq j\), corresponds to an edge connecting vertices \(i\) and \(j\) in the graph). This localization property is important in many graph-based data analysis applications, such as graph spectral filtering [34] and deep learning [5]. Finally, as opposed to other methods that incorporate prior knowledge about \(\mathbf{b}\) into the choice of the approximating polynomial (e.g., [35] considers vectors \(\mathbf{b}\) from a zero-mean distribution with a known covariance matrix), the polynomial approximations resulting from the methods we propose do not depend on \(\mathbf{b}\) or any information about \(\mathbf{b}\). Thus, in applications where the computation of \(f(\mathbf{A})\mathbf{b}\) is repeated for many different vectors \(\mathbf{b}\) with the same \(f\) and \(\mathbf{A}\), the polynomial coefficients only need to be computed a single time. While the classical truncated orthogonal polynomial expansion methods (e.g., Chebyshev, Legendre, [PERSON]) aim to approximate the function \(f\) throughout the full interval \([\underline{\lambda},\overline{\lambda}]\), it is only the polynomial approximation error at the eigenvalues of \(\mathbf{A}\) that affects the overall error in (3). With knowledge of the complete set of eigenvalues, we could do better, for example, by fitting a degree \(K\) polynomial via the discrete least squares problem \(\min_{p\in\mathcal{P}_{K}}\sum_{\ell=1}^{N}\left[f(\lambda_{\ell})-p(\lambda_ {\ell})\right]^{2}\). In Figure 1, we show an example of such a discrete least squares fitting. The resulting approximation error \(||f(\mathbf{A})-p_{K}(\mathbf{A})||_{2}\) for \(K=5\) is \(0.020\), as opposed to \(0.347\) for the degree \(5\) truncated Chebyshev approximation. This is despite the fact that \(\sup_{\lambda\in[\underline{\lambda}]\overline{\lambda}]}|f(\lambda)-p_{K}( \lambda)|\) is equal to \(0.650\) for the discrete least squares approximation, as opposed to \(0.347\) for the Chebyshev approximation. While in our setting we do not have access to the complete set of eigenvalues, our approach in this work is to leverage recent developments in efficiently estimating the spectral density of the matrix \(\mathbf{A}\), to adapt the polynomial to the spectrum in order to achieve better approximation accuracy at the (unknown) eigenvalues. After reviewing spectral density estimation in the next section, we present two new classes of spectrum-adapted approximation techniques in Section 3. In Section 4,we perform numerical experiments, approximating \(f(\mathbf{A})\mathbf{b}\) for different matrices \(\mathbf{A}\) and functions \(f\), and discuss the situations in which the proposed methods work better than the state-of-the-art methods. In Sections 5 and 6, we explore the application of the proposed technique to fast estimation of the norms of localized graph spectral filter dictionary atoms and fast filtering of time-vertex signals, respectively.