## 5 Application I: Estimation of the Norms of Localized Graph Spectral Filter Dictionary Atoms  
A common method to extract information from data residing on a weighted, undirected graph is to represent the graph signal as a linear combination of building block graph signals called atoms, a collection of which is called a dictionary. In this section, we consider localized spectral graph filter dictionaries with the form \(\mathcal{D}=\{\mathbf{\varphi}_{i,l}\}_{i=1,2,\dots,N;\,I=1,2,\dots,L}\), where each atom is defined as \(\mathbf{\varphi}_{i,l}:=f_{l}(\mathbf{L})\delta_{i}\) with \(\mathbf{L}\) being the graph Laplacian and \(\delta_{i}\) having a value of \(1\) at vertex \(i\) and \(0\) elsewhere. Each atom can be interpreted as the result of localizing a spectral pattern characterized by the filter function \(f_{l}\) to be centered at vertex \(i\) in the graph. See [58] for more details about localized spectral graph filter dictionaries and their applications as transforms and regularizers in myriad signal processing and machine learning tasks. For large, sparse graphs, the dictionary atoms are never explicitly computed; rather, their inner products with the graph signal are approximated by \(\langle\mathbf{b},\mathbf{\varphi}_{i,l}\rangle=\delta_{i}^{\top}f_{l}(\mathbf{L })\mathbf{b}\approx\delta_{i}^{\top}p_{l,K}(\mathbf{L})\mathbf{b}\), using polynomial approximation methods such as those described in Section 1 or those proposed in this work. However, in graph signal processing applications such as thresholding for denoising or compression [58; 59; 60] or non-uniform random sampling and interpolation of graph signals [41; 45; 58; 61], it is often important to form a fast estimate of the norms of the dictionary atoms, \(\{||\mathbf{\varphi}_{i,l}||2\}_{i,l}\). Since \(||\mathbf{\varphi}_{i,l}||2=\langle\mathbf{\varphi}_{i,l},\mathbf{\varphi}_{i,l}\rangle= \delta_{i}^{\top}f_{l}^{2}(\mathbf{L})\delta_{i}\) is a bilinear form of the type \(\mathbf{u}^{\top}f(\mathbf{A})\mathbf{u}\), the norm of a single atom can be estimated via quadrature methods such as Lanczos quadrature [53] (Ch. 3.1.7), [56] (Ch. 7), [62]; however, doing this for all \(NL\) atoms is not computationally tractable since each requires a different combination of function and starting vector. Other alternatives include the methods discussed in [63] for estimating diagonal elements of a matrix that is not explicitly available but for which matrix-vector products are easy to evaluate, as \(||\mathbf{\varphi}_{i,l}||_{2}=\sqrt{\left[f_{l}^{2}(\mathbf{L})\right]_{i,l}}\). In this application example, we estimate the norms of the dictionary atoms through the products of matrix functions with random vectors, as follows. Let \(\mathbf{x}\) be a random vector with each component having an independent and identical standard normal distribution (in fact, we are only utilizing the property that the random components have unit variance). Then we have  
\[\text{var}\left(\langle\mathbf{\varphi}_{i,l},\mathbf{x}\rangle\right)=\text{var} \left(\sum_{n=1}^{N}x(n)\varphi_{i,l}(n)\right)=\sum_{n=1}^{N}[\varphi_{i,l}(n )]^{2}\text{var}(x(n))=||\mathbf{\varphi}_{i,l}||_{2}^{2}.\]  
Thus, to estimate \(||\mathbf{\varphi}_{i,l}||_{2}\), it suffices to estimate \(\text{sd}\left(\langle\mathbf{\varphi}_{i,l},\mathbf{x}\rangle\right)=\text{sd} \left(\delta_{i}^{\top}f_{l}(\mathbf{L})\mathbf{x}\right)\approx\text{sd} \left(\delta_{i}^{\top}p_{l,K}(\mathbf{L})\mathbf{x}\right)\) for a degree \(K\) polynomial approximation \(p_{l,K}\) to \(f_{l}\). We therefore define each atom norm estimate as the sample standard deviation  
\[v_{i,l}:=\text{sd}\left(\left\{\delta_{i}^{\top}p_{l,K}(\mathbf{L})\mathbf{x} ^{(j)}\right\}_{j=1,2,\dots,J}\right)\approx||\mathbf{\varphi}_{i,l}||_{2}, \tag{10}\]  
Figure 6: Spectral graph filter bank examples. (**a**) A set of five uniform translates of an itersine kernel \(\sin\left(\frac{\pi}{2}\cos^{2}(\tau x)\right)\)[46; 57]. (**b**) A set of four log-warped translates (also called octave-band or wavelet filters) [46].