Multi-scale geometric methods for data sets. II: Geometric multi-resolution analysis (Q413654)

The concept of a {\textit{geometric multiresolution analysis}} (GMRA) is introduced as a means of analyzing data sets modeled as lying on a potentially low \(d\)-dimensional set inside \(\mathbb{R}^D\), \(D\) large. The construction consists of three main steps: (1) a multi-scale geometric tree decomposition of a given metric space \(\mathcal{M}\) into subsets \(\{C_{j,k}\}_{k\in \mathcal{K}_j,\, j\in\mathbb{Z}}\) called {\textit{dyadic cells}}; (2) a \(d\)-dimensional affine approximation of each \(C_{j,k}\), giving rise to a sequence \(\{\mathcal{M}_j\}_{j\in\mathbb{Z}}\) of piecewise linear sets ({\textit{scaling-like spaces}}); and (3) low-dimensional affine encodings of the differences between \(\mathcal{M}_{j+1}\) and \(\mathcal{M}_j\) (wavelet-like projections). Here, \((\mathcal{M},\mu,\rho)\) is a Borel probability space with \(\mathcal{M}\subset\mathbb{R}^D\). The sequence \(\{C_{j,k}\}\) is analogous to a dyadic cube decomposition. The term geometric wavelets applies because the definitions build on classical multi-scale geometric measure theory. For \(c_{j,k}=\frac{1}{\mu(C_{j,k})}\int_{C_{j,k}} x\, d\mu\) the affine space \(\mathbb{V}_{j,k}=c_{j,k}+V_{j,k}\) with \(V_{j,k}\) spanned by the columns of the matrix \(\Phi_{j,k}\) in the singular value decomposition \(\text{cov}_{j,k}= \Phi\Sigma\Phi^\ast\) of the covariance \(\text{cov}_{j,k}=\mathbb{E}_\mu[(x-c_{j,k})(x-c_{j,k})^\ast|\, x\in C_{j,k}]\) can be thought of as an approximate tangent space to \(\mathcal{M}\) at \(c_{j,k}\) at scale \(j\). Let \(P_{j,k}=\Phi_{j,k}\Phi_{j,k}^\ast\) be the projection matrix onto \(V_{j,k}\) and define the geometric wavelet subspace \(W_{j+1,k}=(I-P_{j,k}) V_{j+1,k}\) and \(\Psi_{j+1,k}\) be the orthogonal matrix of this projection. For \(x\in C_{j,k}\) one sets \(x_j=P_{\mathcal{M}_j}(x)=P_{j,k}(x-c_{j,k})+c_{j,k}\) and \(Q_{\mathcal{M}_{j+1}}(x)=x_{j+1}-x_j\). Then \(P_{\mathcal{M}_{j+1}}=P_{\mathcal{M}_j}+Q_{\mathcal{M}_{j+1}}\) and one says that together the sequence of affine operators forms a GMRA. Further details are worked out in the case of manifolds and {\textit{point cloud}} data and generic algorithms are provided for numerical construction of GMRAs and fast geometric wavelet transforms and their inverses. A series of numerical examples, both synthetic and data driven, is provided. After this, a refined construction of {\textit{orthogonal}} GMRAs is provided which removes redundancies across scales. Again, pseudo-code is provided for this construction. A series of useful variations leading to refined numerical analysis is also provided together with computation cost guidelines.