Abstract
We propose a new approach for nonadaptive dimensionality reduction of manifold-modeled data, demonstrating that a small number of random linear projections can preserve key information about a manifold-modeled signal. We center our analysis on the effect of a random linear projection operator Φ:ℝN→ℝM, M<N, on a smooth well-conditioned K-dimensional submanifold ℳ⊂ℝN. As our main theoretical contribution, we establish a sufficient number M of random projections to guarantee that, with high probability, all pairwise Euclidean and geodesic distances between points on ℳ are well preserved under the mapping Φ.
Our results bear strong resemblance to the emerging theory of Compressed Sensing (CS), in which sparse signals can be recovered from small numbers of random linear measurements. As in CS, the random measurements we propose can be used to recover the original data in ℝN. Moreover, like the fundamental bound in CS, our requisite M is linear in the “information level” K and logarithmic in the ambient dimension N; we also identify a logarithmic dependence on the volume and conditioning of the manifold. In addition to recovering faithful approximations to manifold-modeled signals, however, the random projections we propose can also be used to discern key properties about the manifold. We discuss connections and contrasts with existing techniques in manifold learning, a setting where dimensionality reducing mappings are typically nonlinear and constructed adaptively from a set of sampled training data.
Similar content being viewed by others
References
D. Achlioptas, Database-friendly random projections, in Proc. Symp. on Principles of Database Systems (PODS ’01), pp. 274–281, ACM Press, New York, 2001.
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.
D. Baron, M. B. Wakin, M. F. Duarte, S. Sarvotham, and R. G. Baraniuk, Distributed compressed sensing, Preprint, 2005.
M. Belkin and P. Niyogi, Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput. 15(6) (2003), 1373–1396.
M. Brand, Charting a manifold, in Advances in Neural Information Processing Systems (NIPS), Vol. 15, pp. 985–992, MIT Press, Cambridge, 2003.
D. S. Broomhead and M. Kirby, A new approach for dimensionality reduction: Theory and algorithms, SIAM J. Appl. Math. 60(6) (2000), 2114–2142.
D. S. Broomhead and M. J. Kirby, The Whitney reduction network: A method for computing autoassociative graphs, Neural Comput. 13(11) (2001), 2595–2616.
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.
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.
E. Candès and T. Tao, Decoding via linear programming, IEEE Trans. Inf. Theory 51(12) (2005), 4203–4215.
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.
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.
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.
R. R. Coifman and M. Maggioni, Diffusion wavelets, Appl. Comput. Harmon. Anal. 21(1) (2006), 53–94.
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.
S. Dasgupta and A. Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss, Random Struct. Algorithms 22(1) (2003), 60–65.
D. Donoho, Neighborly polytopes and sparse solution of underdetermined linear equations, Technical Report 2005-04, Department of Statistics, Stanford University, 2005.
D. Donoho, Compressed sensing, IEEE Trans. Inf. Theory 52(4) (2006).
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).
D. Donoho, High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension, Discrete Comput. Geom. 35(4) (2006), 617–652.
D. Donoho and J. Tanner, Neighborliness of randomly-projected simplices in high dimensions, Proc. Natl. Acad. Sci. USA 102(27) (2005), 9452–9457.
D. Donoho and Y. Tsaig, Extensions of compressed sensing, Signal Process. 86(3) (2006), 533–548.
D. L. Donoho and C. Grimes, Image manifolds which are isometric to Euclidean space, J. Math. Imaging Comput. Vis. 23(1) (2005), 5–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.
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.
C. Grimes, New Methods in Nonlinear Dimensionality Reduction, Ph.D. thesis, Department of Statistics, Stanford University, 2003.
J. Haupt and R. Nowak, Signal reconstruction from noisy random projections, IEEE Trans. Inf. Theory 52(9) (2006), 4036–4048.
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.
M. W. Hirsch, Differential Topology, Graduate Texts in Mathematics, Vol. 33, Springer, New York, 1976.
P. Indyk and A. Naor, Nearest-neighbor-preserving embeddings, ACM Trans. Algorithms 3(3) (2007).
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.
G. G. Lorentz, M. von Golitschek, and Y. Makovoz, Constructive Approximation: Advanced Problems, Grundlehren der Mathematischen Wissenschaften, Vol. 304, Springer, Berlin, 1996.
S. Mallat, A Wavelet Tour of Signal Processing, Academic Press, San Diego, 1999.
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.
A. Pinkus, n-Widths and Optimal Recovery, in Proceedings of Symposia in Applied Mathematics, Vol. 36, pp. 51–66, American Mathematical Society, Providence, 1986.
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.
S. T. Roweis and L. K. Saul, Nonlinear dimensionality reduction by locally linear embedding, Science 290(5500) (2000), 2323–2326.
M. Rudelson and R. Vershynin, Geometric approach to error correcting codes and reconstruction of signals, Int. Math. Res. Not. 64 (2005), 4019–4041.
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.
D. S. Taubman and M. W. Marcellin, JPEG 2000: Image Compression Fundamentals, Standards and Practice, Kluwer Academic, Dordrecht, 2001.
J. B. Tenenbaum, V. de Silva, and J. C. Langford, A global geometric framework for nonlinear dimensionality reduction, Science 290(5500) (2000), 2319–2323.
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.
M. Turk and A. Pentland, Eigenfaces for recognition, J. Cogn. Neurosci. 3(1) (1991), 71–83.
M. B. Wakin, The Geometry of Low-Dimensional Signal Models, Ph.D. thesis, Department of Electrical and Computer Engineering, Rice University, Houston, TX, 2006.
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.
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.
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).
Z. Zhang and H. Zha, Principal manifolds and nonlinear dimension reduction via tangent space alignment, SIAM J. Sci. Comput. 26(1) (2005), 313–338.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Emmanuel Candès.
This research was supported by ONR grants N00014-06-1-0769 and N00014-06-1-0829; AFOSR grant FA9550-04-0148; DARPA grants N66001-06-1-2011 and N00014-06-1-0610; NSF grants CCF-0431150, CNS-0435425, CNS-0520280, and DMS-0603606; and the Texas Instruments Leadership University Program. Web: dsp.rice.edu/cs.
Rights and permissions
About this article
Cite this article
Baraniuk, R.G., Wakin, M.B. Random Projections of Smooth Manifolds. Found Comput Math 9, 51–77 (2009). https://doi.org/10.1007/s10208-007-9011-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10208-007-9011-z
Keywords
- Manifolds
- Dimensionality reduction
- Random projections
- Compressed sensing
- Sparsity
- Manifold learning
- Johnson–Lindenstrauss lemma