Random projections of smooth manifolds. (English) Zbl 1172.53005

Consider a compact \(K\)-dimensional Riemannian submanifold \({\mathcal M} \subset\mathbb R^N\) and denote by \(\Phi\) a random orthoprojection operator from \(\mathbb R^N\) onto \(\mathbb R^M\). The main theorem of this article states that with probability at least \(1-\rho\) the distance (or geodesic distance) between any two points \(x\), \(y\in{\mathcal M}\) is roughly preserved by \(\Phi\) provided
\[ M = O\biggl(\frac{K \log(NVR\tau^{-1}\varepsilon^{-1})\log(1/\rho)}{\varepsilon^2}\biggr) \leq N. \]
In this formula \(V\) is the volume of \({\mathcal M}\), \(R\) its geodesic covering regularity, and \(1/\tau\) its condition number. The positive real \(\varepsilon\) determines the desired accuracy of length preservation. An explicit bound (not just the order of magnitude) for \(M\) can be extracted from the proof. This result is similar to a theorem by Johnson and Lindenstrauss on distance preservation under random orthoprojections of a finite point cloud.
The article also contains an introduction to applications of “dimension reduction techniques” in general and a discussion of ideas for the application of the above result in the context of compressed sensing and manifold learning.


53A07 Higher-dimensional and -codimensional surfaces in Euclidean and related \(n\)-spaces
62H99 Multivariate analysis
65C99 Probabilistic methods, stochastic differential equations
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68T05 Learning and adaptive systems in artificial intelligence
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
94A29 Source coding
Full Text: DOI Link


[1] D. Achlioptas, Database-friendly random projections, in Proc. Symp. on Principles of Database Systems (PODS ’01), pp. 274–281, ACM Press, New York, 2001.
[2] R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, A simple proof of the restricted isometry property for random matrices. Constr. Approx. (2008), to appear. · Zbl 1177.15015
[3] D. Baron, M. B. Wakin, M. F. Duarte, S. Sarvotham, and R. G. Baraniuk, Distributed compressed sensing, Preprint, 2005.
[4] M. Belkin and P. Niyogi, Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput. 15(6) (2003), 1373–1396. · Zbl 1085.68119
[5] M. Brand, Charting a manifold, in Advances in Neural Information Processing Systems (NIPS), Vol. 15, pp. 985–992, MIT Press, Cambridge, 2003.
[6] D. S. Broomhead and M. Kirby, A new approach for dimensionality reduction: Theory and algorithms, SIAM J. Appl. Math. 60(6) (2000), 2114–2142. · Zbl 1038.65013
[7] D. S. Broomhead and M. J. Kirby, The Whitney reduction network: A method for computing autoassociative graphs, Neural Comput. 13(11) (2001), 2595–2616. · Zbl 1003.68112
[8] E. Candès, J. Romberg, and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory 52(2) (2006), 489–509. · Zbl 1231.94017
[9] E. Candès, J. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math. 59(8) (2006), 1207–1223. · Zbl 1098.94009
[10] E. Candès and T. Tao, Decoding via linear programming, IEEE Trans. Inf. Theory 51(12) (2005), 4203–4215. · Zbl 1264.94121
[11] E. Candès and T. Tao, The Dantzig selector: Statistical estimation when p is much larger than n, Ann. Stat. (2007), to appear. arXiv: math.ST/0506081. · Zbl 1139.62019
[12] E. Candès and T. Tao, Near optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. Inf. Theory 52(12) (2006), 5406–5425. · Zbl 1309.94033
[13] G. Carlsson, A. Zomorodian, A. Collins, and L. Guibas, Persistence bar codes for shapes, in Proc. Symp. on Geometry processing (SGP ’04), pp. 124–135, ACM Press, New York, 2004.
[14] R. R. Coifman and M. Maggioni, Diffusion wavelets, Appl. Comput. Harmon. Anal. 21(1) (2006), 53–94. · Zbl 1095.94007
[15] J. A. Costa and A. O. Hero, Geodesic entropic graphs for dimension and entropy estimation in manifold learning, IEEE Trans. Signal Process. 52(8) (2004), 2210–2221. · Zbl 1369.68278
[16] S. Dasgupta and A. Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss, Random Struct. Algorithms 22(1) (2003), 60–65. · Zbl 1018.51010
[17] D. Donoho, Neighborly polytopes and sparse solution of underdetermined linear equations, Technical Report 2005-04, Department of Statistics, Stanford University, 2005.
[18] D. Donoho, Compressed sensing, IEEE Trans. Inf. Theory 52(4) (2006). · Zbl 1288.94016
[19] D. Donoho, For most large underdetermined systems of linear equations, the minimal L1-norm solution is also the sparsest solution, Commun. Pure Appl. Math. 59(6) (2006). · Zbl 1113.15004
[20] D. Donoho, High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension, Discrete Comput. Geom. 35(4) (2006), 617–652. · Zbl 1095.52500
[21] D. Donoho and J. Tanner, Neighborliness of randomly-projected simplices in high dimensions, Proc. Natl. Acad. Sci. USA 102(27) (2005), 9452–9457. · Zbl 1135.60300
[22] D. Donoho and Y. Tsaig, Extensions of compressed sensing, Signal Process. 86(3) (2006), 533–548. · Zbl 1163.94329
[23] D. L. Donoho and C. Grimes, Image manifolds which are isometric to Euclidean space, J. Math. Imaging Comput. Vis. 23(1) (2005), 5–24. · Zbl 1478.62186
[24] D. L. Donoho and C. E. Grimes, Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data, Proc. Natl. Acad. Sci. USA 100(10) (2003), 5591–5596. · Zbl 1130.62337
[25] D. L. Donoho and J. Tanner, Counting faces of randomly-projected polytopes when then projection radically lowers dimension, Technical Report 2006-11, Department of Statistics, Stanford University, 2006. arXiv: math.MG/0607364. · Zbl 1206.52010
[26] C. Grimes, New Methods in Nonlinear Dimensionality Reduction, Ph.D. thesis, Department of Statistics, Stanford University, 2003.
[27] J. Haupt and R. Nowak, Signal reconstruction from noisy random projections, IEEE Trans. Inf. Theory 52(9) (2006), 4036–4048. · Zbl 1323.94046
[28] G. E. Hinton, P. Dayan, and M. Revow, Modeling the manifolds of images of handwritten digits, IEEE Trans. Neural Netw. 8(1) (1997), 65–74.
[29] M. W. Hirsch, Differential Topology, Graduate Texts in Mathematics, Vol. 33, Springer, New York, 1976.
[30] P. Indyk and A. Naor, Nearest-neighbor-preserving embeddings, ACM Trans. Algorithms 3(3) (2007). · Zbl 1192.68748
[31] S. Kirolos, J. Laska, M. Wakin, M. Duarte, D. Baron, T. Ragheb, Y. Massoud, and R. Baraniuk, Analog-to-information conversion via random demodulation, Proc. IEEE Dallas Circuits and Systems Workshop (DCAS), Dallas, TX, October 2006.
[32] G. G. Lorentz, M. von Golitschek, and Y. Makovoz, Constructive Approximation: Advanced Problems, Grundlehren der Mathematischen Wissenschaften, Vol. 304, Springer, Berlin, 1996. · Zbl 0910.41001
[33] S. Mallat, A Wavelet Tour of Signal Processing, Academic Press, San Diego, 1999. · Zbl 0998.94510
[34] P. Niyogi, S. Smale, and S. Weinberger, Finding the homology of submanifolds with confidence from random samples, Discrete Comput. Geom. (2006). doi: 10.1007/s00454-006-1250-7 . · Zbl 1148.68048
[35] A. Pinkus, n-Widths and Optimal Recovery, in Proceedings of Symposia in Applied Mathematics, Vol. 36, pp. 51–66, American Mathematical Society, Providence, 1986.
[36] I. Ur Rahman, I. Drori, V. C. Stodden, D. L. Donoho, and P. Schroeder, Multiscale representations for manifold-valued data, SIAM J. Multiscale Model. Simul. 4(4) (2005), 1201–1232. · Zbl 1236.65166
[37] S. T. Roweis and L. K. Saul, Nonlinear dimensionality reduction by locally linear embedding, Science 290(5500) (2000), 2323–2326.
[38] M. Rudelson and R. Vershynin, Geometric approach to error correcting codes and reconstruction of signals, Int. Math. Res. Not. 64 (2005), 4019–4041. · Zbl 1103.94014
[39] D. Takhar, V. Bansal, M. Wakin, M. Duarte, D. Baron, K. F. Kelly, and R. G. Baraniuk, A compressed sensing camera: New theory and an implementation using digital micromirrors, Proc. Comp. Imaging IV at SPIE Electronic Imaging, San Jose, CA, January 2006.
[40] D. S. Taubman and M. W. Marcellin, JPEG 2000: Image Compression Fundamentals, Standards and Practice, Kluwer Academic, Dordrecht, 2001.
[41] J. B. Tenenbaum, V. de Silva, and J. C. Langford, A global geometric framework for nonlinear dimensionality reduction, Science 290(5500) (2000), 2319–2323.
[42] J. A. Tropp, M. B. Wakin, M. F. Duarte, D. Baron, and R. G. Baraniuk, Random filters for compressive sampling and reconstruction, in Proc. Int. Conf. Acoustics, Speech, Signal Processing (ICASSP), IEEE, New York, 2006.
[43] M. Turk and A. Pentland, Eigenfaces for recognition, J. Cogn. Neurosci. 3(1) (1991), 71–83.
[44] M. B. Wakin, The Geometry of Low-Dimensional Signal Models, Ph.D. thesis, Department of Electrical and Computer Engineering, Rice University, Houston, TX, 2006.
[45] M. B. Wakin and R. G. Baraniuk, Random projections of signal manifolds, in Proc. Int. Conf. Acoustics, Speech, Signal Processing (ICASSP), IEEE, New York, 2006. · Zbl 1172.53005
[46] M. B. Wakin, D. L. Donoho, H. Choi, and R. G. Baraniuk, The multiscale structure of non-differentiable image manifolds, in Proc. Wavelets XI at SPIE Optics and Photonics, San Diego, CA, August 2005.
[47] K. Q. Weinberger and L. K. Saul, Unsupervised learning of image manifolds by semidefinite programming, Int. J. Comput. Vis. 70(1) (2006), 77–90. Special issue: Comput. Vis. Pattern Recognit. (CVPR 2004). · Zbl 05062738
[48] Z. Zhang and H. Zha, Principal manifolds and nonlinear dimension reduction via tangent space alignment, SIAM J. Sci. Comput. 26(1) (2005), 313–338. · Zbl 1077.65042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.