Random Projections of Smooth Manifolds

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.