  High-dimensional datasets are well-approximated by low-dimensional
structures. Over the past decade, this empirical observation motivated the
investigation of detection, measurement, and modeling techniques to exploit
these low-dimensional intrinsic structures, yielding numerous implications for
high-dimensional statistics, machine learning, and signal processing. Manifold
learning (where the low-dimensional structure is a manifold) and dictionary
learning (where the low-dimensional structure is the set of sparse linear
combinations of vectors from a finite dictionary) are two prominent theoretical
and computational frameworks in this area. Despite their ostensible
distinction, the recently-introduced Geometric Multi-Resolution Analysis (GMRA)
provides a robust, computationally efficient, multiscale procedure for
simultaneously learning manifolds and dictionaries.
  In this work, we prove non-asymptotic probabilistic bounds on the
approximation error of GMRA for a rich class of data-generating statistical
models that includes "noisy" manifolds, thereby establishing the theoretical
robustness of the procedure and confirming empirical observations. In
particular, if a dataset aggregates near a low-dimensional manifold, our
results show that the approximation error of the GMRA is completely independent
of the ambient dimension. Our work therefore establishes GMRA as a provably
fast algorithm for dictionary learning with approximation and sparsity
guarantees. We include several numerical experiments confirming these
theoretical results, and our theoretical framework provides new tools for
assessing the behavior of manifold learning and dictionary learning procedures
on a large class of interesting models.
