Adaptive Geometric Multiscale Approximations for Intrinsically Low-dimensional Data
Adaptive Geometric Multiscale Approximations for Intrinsically Low-dimensional Data
复制标题
DOI：
--
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
Wenjing Liao;M. Maggioni
中科院分区：
文献类型：
--
作者：
Wenjing Liao;M. Maggioni
我们考虑有效逼近和编码从 $\mathbb{R}^D$ 中的概率分布 $\rho$ 采样的高维数据的问题，该数据几乎在 $d$ 维集合 $\mathcal{M}$ 上得到支持 - 例如在 $d$ 维黎曼流形上得到支持。几何多分辨率分析（GMRA）提供了一个强大且计算高效的程序来构建不同分辨率下 $\mathcal{M}$ 的低维几何近似。我们引入了几何小波系数的阈值算法，从而产生了我们所说的自适应 GMRA 近似。我们表明，当阈值被选择为样本数量 $n$ 的合适通用函数时，这些数据驱动的经验近似表现良好，在各种度量 $\rho$ 上，允许在不同的尺度和位置表现出不同的规律性，从而有效地从比流形支持的度量更复杂的度量中编码数据。这些近似产生数据驱动的字典，以及将数据映射到系数的快速变换，以及这种映射的逆。字典构建和变换的算法的复杂度为 $C n \log n$，其中 $D$ 为线性常量，$d$ 为指数常量。因此，我们的工作将自适应 GMRA 建立为具有近似保证的快速字典学习算法。我们对合成数据和真实数据进行了多次数值实验，证实了我们的理论结果并证明了自适应 GMRA 的有效性。
We consider the problem of efficiently approximating and encoding high-dimensional data sampled from a probability distribution $\rho$ in $\mathbb{R}^D$, that is nearly supported on a $d$-dimensional set $\mathcal{M}$ - for example supported on a $d$-dimensional Riemannian manifold. Geometric Multi-Resolution Analysis (GMRA) provides a robust and computationally efficient procedure to construct low-dimensional geometric approximations of $\mathcal{M}$ at varying resolutions. We introduce a thresholding algorithm on the geometric wavelet coefficients, leading to what we call adaptive GMRA approximations. We show that these data-driven, empirical approximations perform well, when the threshold is chosen as a suitable universal function of the number of samples $n$, on a wide variety of measures $\rho$, that are allowed to exhibit different regularity at different scales and locations, thereby efficiently encoding data from more complex measures than those supported on manifolds. These approximations yield a data-driven dictionary, together with a fast transform mapping data to coefficients, and an inverse of such a map. The algorithms for both the dictionary construction and the transforms have complexity $C n \log n$ with the constant linear in $D$ and exponential in $d$. Our work therefore establishes adaptive GMRA as a fast dictionary learning algorithm with approximation guarantees. We include several numerical experiments on both synthetic and real data, confirming our theoretical results and demonstrating the effectiveness of adaptive GMRA.