Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
An Invitation to Compressive Sensing Read chapter Read first chapter

2013 | OriginalPaper | Chapter

12. Random Sampling in Bounded Orthonormal Systems

Authors : Simon Foucart, Holger Rauhut

Published in: A Mathematical Introduction to Compressive Sensing

Publisher: Springer New York

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This chapter considers the recovery of signals with a sparse expansion in a bounded orthonormal system. After an inventory of such bounded orthonormal systems including the Fourier systems, theoretical limitations specific to this situation are obtained for the minimal number of samples. Then, using this number of random samples, nonuniform sparse recovery is proved to be possible via ℓ1-minimization. Next, using a slightly higher number of random samples, uniform sparse recovery is also proved to be possible via a variety of algorithms. This is derived via establishing the restricted isometry property for the associated random sampling matrix—the random partial Fourier matrix is a particular case. Finally, a connection to the Λ 1-problem is pointed out.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Instance Optimality and Quotient Property
next chapter Lossless Expanders in Compressive Sensing
Literature
1.
P. Abrial, Y. Moudden, J.-L. Starck, J. Fadili, J. Delabrouille, M. Nguyen, CMB data analysis and sparsity. Stat. Meth. 5, 289–298 (2008)MathSciNetMATHCrossRef
7.
N. Ailon, B. Chazelle, The fast Johnson-Lindenstrauss transform and approximate nearest neighbors. SIAM J. Comput. 39(1), 302–322 (2009)MathSciNetMATHCrossRef
8.
N. Ailon, E. Liberty, Fast dimension reduction using Rademacher series on dual BCH codes. Discrete Comput. Geom. 42(4), 615–630 (2009)MathSciNetMATHCrossRef
9.
N. Ailon, E. Liberty, Almost optimal unrestricted fast Johnson-Lindenstrauss transform. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, USA, 22–25 January 2011
10.
N. Ailon, H. Rauhut, Fast and RIP-optimal transforms. Preprint (2013)
17.
G. Andrews, R. Askey, R. Roy, in Special Functions. Encyclopedia of Mathematics and its Applications, vol. 71 (Cambridge University Press, Cambridge, 1999)
26.
W. Bajwa, J. Haupt, G. Raz, S. Wright, R. Nowak, Toeplitz-structured compressed sensing matrices. In Proc. IEEE Stat. Sig. Proc. Workshop, pp. 294–298, 2007
62.
63.
J. Bourgain, \(\Lambda _{p}\)-sets in analysis: results, problems and related aspects. In Handbook of the Geometry of Banach Spaces, vol. 1, ed. by W. B. Johnson, J. Lindenstrauss (North-Holland, Amsterdam, 2001), pp. 195–232
80.
N. Burq, S. Dyatlov, R. Ward, M. Zworski, Weighted eigenfunction estimates with applications to compressed sensing. SIAM J. Math. Anal. 44(5), 3481–3501 (2012)MathSciNetMATHCrossRef
88.
E.J. Candès, Y. Plan, A probabilistic and RIPless theory of compressed sensing. IEEE Trans. Inform. Theor. 57(11), 7235–7254 (2011)CrossRef
92.
E.J. Candès, J. Romberg, Quantitative robust uncertainty principles and optimally sparse decompositions. Found. Comput. Math. 6(2), 227–254 (2006)MathSciNetMATHCrossRef
93.
E.J. Candès, J. Romberg, Sparsity and incoherence in compressive sampling. Inverse Probl. 23(3), 969–985 (2007)MATHCrossRef
94.
E.J. Candès, J. Romberg, T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theor. 52(2), 489–509 (2006)MATHCrossRef
97.
E.J. Candès, T. Tao, Near optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inform. Theor. 52(12), 5406–5425 (2006)CrossRef
103.
D. Chafaï, O. Guédon, G. Lecué, A. Pajor, Interactions Between Compressed Sensing, Random Matrices and High-dimensional Geometry, Panoramas et Synthèses, vol. 37 (Société Mathématique de France, to appear)
115.
M. Cheraghchi, V. Guruswami, A. Velingker, Restricted isometry of Fourier matrices and list decodability of random linear codes. Preprint (2012)
117.
T. Chihara, An Introduction to Orthogonal Polynomials (Gordon and Breach Science Publishers, New York 1978)MATH
119.
O. Christensen, An Introduction to Frames and Riesz Bases. Applied and Numerical Harmonic Analysis (Birkhäuser, Boston, 2003)MATH
122.
A. Cohen, Numerical Analysis of Wavelet Methods (North-Holland, Amsterdam, 2003)MATH
126.
137.
I. Daubechies, Ten Lectures on Wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 61 (SIAM, Philadelphia, 1992)
158.
164.
181.
M. Elad, A.M. Bruckstein, A generalized uncertainty principle and sparse representation in pairs of bases. IEEE Trans. Inform. Theor. 48(9), 2558–2567 (2002)MathSciNetMATHCrossRef
191.
H.G. Feichtinger, F. Luef, T. Werther, A guided tour from linear algebra to the foundations of Gabor analysis. In Gabor and Wavelet Frames. Lecture Notes Series, Institute for Mathematical Sciences National University of Singapore, vol. 10 (World Sci. Publ., Hackensack, 2007), pp. 1–49
192.
H.G. Feichtinger, T. Strohmer, Gabor Analysis and Algorithms: Theory and Applications (Birkhäuser, Boston, 1998)MATHCrossRef
198.
G.B. Folland, Fourier Analysis and Its Applications (Wadsworth and Brooks, Pacific Grove, 1992)MATH
199.
G.B. Folland, A Course in Abstract Harmonic Analysis (CRC Press, Boca Raton, 1995)MATH
200.
223.
A.C. Gilbert, S. Muthukrishnan, S. Guha, P. Indyk, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC ’02, pp. 152–161, ACM, New York, NY, USA, 2002
231.
G. Golub, C.F. van Loan, Matrix Computations, 3rd edn. (The Johns Hopkins University Press, Baltimore, MD, 1996)MATH
236.
L. Grafakos, Modern Fourier Analysis, 2nd edn. Graduate Texts in Mathematics, vol. 250 (Springer, New York, 2009)
244.
K. Gröchenig, Foundations of Time-Frequency Analysis. Applied and Numerical Harmonic Analysis (Birkhäuser, Boston, MA, 2001)
245.
D. Gross, Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inform. Theor. 57(3), 1548–1566 (2011)CrossRef
248.
O. Guédon, S. Mendelson, A. Pajor, N. Tomczak-Jaegermann, Majorizing measures and proportional subsets of bounded orthonormal systems. Rev. Mat. Iberoam. 24(3), 1075–1095 (2008)MathSciNetMATHCrossRef
261.
H. Hassanieh, P. Indyk, D. Katabi, E. Price, Nearly optimal sparse Fourier transform. In Proceedings of the 44th Symposium on Theory of Computing, STOC ’12, pp. 563–578, ACM, New York, NY, USA, 2012
263.
J. Haupt, W. Bajwa, G. Raz, R. Nowak, Toeplitz compressed sensing matrices with applications to sparse channel estimation. IEEE Trans. Inform. Theor. 56(11), 5862–5875 (2010)MathSciNetCrossRef
265.
D. Healy Jr., D. Rockmore, P. Kostelec, S. Moore, FFTs for the 2-Sphere—Improvements and Variations. J. Fourier Anal. Appl. 9(4), 341–385 (2003)MathSciNetMATHCrossRef
268.
M. Herman, T. Strohmer, High-resolution radar via compressed sensing. IEEE Trans. Signal Process. 57(6), 2275–2284 (2009)MathSciNetCrossRef
274.
A. Hinrichs, J. Vybiral, Johnson-Lindenstrauss lemma for circulant matrices. Random Struct. Algorithm. 39(3), 391–398 (2011)MathSciNetMATH
283.
M. Hügel, H. Rauhut, T. Strohmer, Remote sensing via ℓ 1-minimization. Found. Comput. Math., to appear. (2012)
287.
288.
M. Iwen, Improved approximation guarantees for sublinear-time Fourier algorithms. Appl. Comput. Harmon. Anal. 34(1), 57–82 (2013)MathSciNetMATHCrossRef
289.
M. Iwen, A. Gilbert, M. Strauss, Empirical evaluation of a sub-linear time sparse DFT algorithm. Commun. Math. Sci. 5(4), 981–998 (2007)MathSciNetMATH
292.
R. James, M. Dennis, N. Daniel, Fast discrete polynomial transforms with applications to data analysis for distance transitive graphs. SIAM J. Comput. 26(4), 1066–1099 (1997)MathSciNetCrossRef
307.
F. Krahmer, S. Mendelson, H. Rauhut, Suprema of chaos processes and the restricted isometry property. Comm. Pure Appl. Math. (to appear)
308.
F. Krahmer, G.E. Pfander, P. Rashkov, Uncertainty principles for time–frequency representations on finite abelian groups. Appl. Comput. Harmon. Anal. 25(2), 209–225 (2008)MathSciNetMATHCrossRef
309.
F. Krahmer, R. Ward, New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property. SIAM J. Math. Anal. 43(3), 1269–1281 (2011)MathSciNetMATHCrossRef
310.
F. Krahmer, R. Ward, Beyond incoherence: stable and robust sampling strategies for compressive imaging. Preprint (2012)
311.
314.
P. Kuppinger, G. Durisi, H. Bölcskei, Uncertainty relations and sparse signal recovery for pairs of general signal sets. IEEE Trans. Inform. Theor. 58(1), 263–277 (2012)CrossRef
317.
J. Lawrence, G.E. Pfander, D. Walnut, Linear independence of Gabor systems in finite dimensional vector spaces. J. Fourier Anal. Appl. 11(6), 715–726 (2005)MathSciNetMATHCrossRef
341.
S. Mallat, A Wavelet Tour of Signal Processing. Middleton Academic Press, San Diego, 1998MATH
352.
D. Middleton, Channel Modeling and Threshold Signal Processing in Underwater Acoustics: An Analytical Overview. IEEE J. Oceanic Eng. 12(1), 4–28 (1987)MathSciNetCrossRef
384.
G. Pfander, H. Rauhut, J. Tanner, Identification of matrices having a sparse representation. IEEE Trans. Signal Process. 56(11), 5376–5388 (2008)MathSciNetCrossRef
385.
G. Pfander, H. Rauhut, J. Tropp, The restricted isometry property for time-frequency structured random matrices. Prob. Theor. Relat. Field. to appear
390.
M. Pinsky, Introduction to Fourier Analysis and Wavelets. Graduate Studies in Mathematics, vol. 102 (American Mathematical Society, Providence, RI, 2009)
398.
399.
400.
D. Potts, G. Steidl, M. Tasche, Fast fourier transforms for nonequispaced data: a tutorial. In Modern Sampling Theory: Mathematics and Applications ed. by J. Benedetto, P. Ferreira, Chap. 12 (Birkhäuser, Boston, 2001), pp. 247–270
408.
409.
H. Rauhut, On the impossibility of uniform sparse reconstruction using greedy methods. Sampl. Theor. Signal Image Process. 7(2), 197–215 (2008)MathSciNetMATH
410.
H. Rauhut, Circulant and Toeplitz matrices in compressed sensing. In Proc. SPARS’09 (Saint-Malo, France, 2009)
411.
H. Rauhut, Compressive sensing and structured random matrices. In Theoretical Foundations and Numerical Methods for Sparse Recovery, ed. by M. Fornasier. Radon Series on Computational and Applied Mathematics, vol. 9 (de Gruyter, Berlin, 2010), pp. 1–92
412.
413.
H. Rauhut, J.K. Romberg, J.A. Tropp, Restricted isometries for partial random circulant matrices. Appl. Comput. Harmon. Anal. 32(2), 242–254 (2012)MathSciNetMATHCrossRef
415.
H. Rauhut, R. Ward, Sparse recovery for spherical harmonic expansions. In Proc. SampTA 2011, Singapore, 2011
416.
417.
B. Recht, A simpler approach to matrix completion. J. Mach. Learn. Res. 12, 3413–3430 (2011)MathSciNet
433.
M. Rudelson, R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements. Comm. Pure Appl. Math. 61, 1025–1045 (2008)MathSciNetMATHCrossRef
437.
W. Rudin, Fourier Analysis on Groups (Interscience Publishers, New York, 1962)MATH
445.
I. Segal, M. Iwen, Improved sparse Fourier approximation results: Faster implementations and stronger guarantees. Numer. Algorithm. 63(2), 239–263 (2013)MathSciNetMATHCrossRef
452.
E.M. Stein, R. Shakarchi, Functional Analysis: Introduction to Further Topics in Analysis. Princeton Lectures in Analysis, vol. 4 (Princeton University Press, Princeton, NJ, 2011)
453.
M. Stojanovic, Underwater Acoustic Communications. In Encyclopedia of Electrical and Electronics Engineering, vol. 22, ed. by M. Stojanovic, J. G. Webster (Wiley, New York, 1999), pp. 688–698
458.
G. Szegő, Orthogonal Polynomials, 4th edn. (American Mathematical Society, Providence, 1975)
464.
481.
488.
J.A. Tropp, J.N. Laska, M.F. Duarte, J.K. Romberg, R.G. Baraniuk, Beyond Nyquist: Efficient sampling of sparse bandlimited signals. IEEE Trans. Inform. Theor. 56(1), 520–544 (2010)MathSciNetCrossRef
489.
J.A. Tropp, M. Wakin, M. Duarte, D. Baron, R. Baraniuk, Random filters for compressive sampling and reconstruction. Proc. 2006 IEEE International Conference Acoustics, Speech, and Signal Processing, vol. 3, pp. 872–875, 2006
491.
502.
505.
J. Walker, Fourier analysis and wavelet analysis. Notices Am. Math. Soc. 44(6), 658–670 (1997)MATH
508.
P. Wojtaszczyk, A Mathematical Introduction to Wavelets (Cambridge University Press, Cambridge, 1997)MATHCrossRef
519.
J. Zou, A.C. Gilbert, M. Strauss, I. Daubechies, Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis. J. Comput. Phys. 211, 572–595 (2005)MathSciNetCrossRef
Metadata
Title
Random Sampling in Bounded Orthonormal Systems
Authors
Simon Foucart
Holger Rauhut
Copyright Year
2013
Publisher
Springer New York
Book
A Mathematical Introduction to Compressive Sensing

Print ISBN: 978-0-8176-4947-0

Electronic ISBN: 978-0-8176-4948-7

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-0-8176-4948-7_12

Premium Partner

    Image Credits