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:
On Repeated Sequential Closures of Constructible Functions in Valuations Read chapter Read first chapter

2017 | OriginalPaper | Chapter

The Restricted Isometry Property of Subsampled Fourier Matrices

Authors : Ishay Haviv, Oded Regev

Published in: Geometric Aspects of Functional Analysis

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

A matrix \(A \in \mathbb{C}^{q\times N}\) satisfies the restricted isometry property of order k with constant ε if it preserves the ℓ 2 norm of all k-sparse vectors up to a factor of 1 ±ε. We prove that a matrix A obtained by randomly sampling q = O(k ⋅ log2 k ⋅ logN) rows from an N × N Fourier matrix satisfies the restricted isometry property of order k with a fixed ε with high probability. This improves on Rudelson and Vershynin (Comm Pure Appl Math, 2008), its subsequent improvements, and Bourgain (GAFA Seminar Notes, 2014).

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 On the Expectation of Operator Norms of Random Matrices
next chapter Upper Bound for the Dvoretzky Dimension in Milman-Schechtman Theorem
Footnotes
1
A preliminary version appeared in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016, pages 288–297.
 
2
Note that the list-decoding result of [14] was later improved by Wootters [33] using different techniques.
 
3
The result in [19] is weaker in two main respects. First, it is restricted to the case that Ax is in {0, 1} q . This significantly simplifies the analysis and leads to a better bound on the number of rows of A. Second, the order of quantifiers is switched, namely it shows that for any sparse x, a random subsampled A works with high probability, whereas for the restricted isometry property we need to show that a random A works for all sparse x.
 
Literature
1.
N. Ailon, B. Chazelle, The fast Johnson–Lindenstrauss transform and approximate nearest neighbors. SIAM J. Comput. 39 (1), 302–322 (2009). Preliminary version in STOC’06
2.
N. Ailon, E. Liberty, Fast dimension reduction using Rademacher series on dual BCH codes. Discrete Comput. Geom. 42 (4), 615–630 (2009). Preliminary version in SODA’08
3.
N. Ailon, E. Liberty, An almost optimal unrestricted fast Johnson–Lindenstrauss transform. ACM Trans. Algorithms 9 (3), 21 (2013). Preliminary version in SODA’11
4.
A.S. Bandeira, E. Dobriban, D.G. Mixon, W.F. Sawin, Certifying the restricted isometry property is hard. IEEE Trans. Inform. Theory 59 (6), 3448–3450 (2013)MathSciNetCrossRef
5.
A.S. Bandeira, M.E. Lewis, D.G. Mixon, Discrete uncertainty principles and sparse signal processing. CoRR abs/1504.01014 (2015)
6.
R. Baraniuk, M. Davenport, R. DeVore, M. Wakin, A simple proof of the restricted isometry property for random matrices. Constr. Approx. 28 (3), 253–263 (2008)MathSciNetCrossRefMATH
7.
J. Bourgain, An improved estimate in the restricted isometry problem, in Geometric Aspects of Functional Analysis. Lecture Notes in Mathematics, vol. 2116, pp. 65–70 (Springer, Berlin, 2014)
8.
E.J. Candès, The restricted isometry property and its implications for compressed sensing. C. R. Math. 346 (9–10), 589–592 (2008)MathSciNetCrossRefMATH
9.
10.
E.J. Candès, T. Tao, Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. on Inform. Theory 52 (12), 5406–5425 (2006)MathSciNetCrossRefMATH
11.
E.J. Candès, M. Rudelson, T. Tao, R. Vershynin, Error correction via linear programming, in 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 295–308 (2005)
12.
E.J. Candès, J.K. Romberg, T. Tao, Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59 (8), 1207–1223 (2006)MathSciNetCrossRefMATH
13.
14.
M. Cheraghchi, V. Guruswami, A. Velingker, Restricted isometry of Fourier matrices and list decodability of random linear codes. SIAM J. Comput. 42 (5), 1888–1914 (2013). Preliminary version in SODA’13
15.
16.
D.L. Donoho, M. Elad, V.N. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Inform. Theory 52 (1), 6–18 (2006)MathSciNetCrossRefMATH
17.
S. Foucart, A. Pajor, H. Rauhut, T. Ullrich, The Gelfand widths of ℓ p -balls for 0 < p ≤ 1. J. Complex. 26 (6), 629–640 (2010)
18.
A.Y. Garnaev, E.D. Gluskin, On the widths of Euclidean balls. Sov. Math. Dokl. 30, 200–203 (1984)MATH
19.
I. Haviv, O. Regev, The list-decoding size of Fourier-sparse boolean functions, in Proceedings of the 30th Conference on Computational Complexity, CCC, pp. 58–71 (2015)
20.
P. Indyk, I. Razenshteyn, On model-based RIP-1 matrices, in Automata, Languages, and Programming - 40th International Colloquium, ICALP, pp. 564–575 (2013)
21.
A.C. Kak, M. Slaney, Principles of Computerized Tomographic Imaging (Society of Industrial and Applied Mathematics, Philadelphia, 2001)CrossRefMATH
22.
F. Krahmer, R. Ward, New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property. SIAM J. Math. Anal. 43 (3), 1269–1281 (2011)MathSciNetCrossRefMATH
23.
F. Krahmer, S. Mendelson, H. Rauhut, Suprema of chaos processes and the restricted isometry property. CoRR abs/1207.0235 (2012)
24.
C. McDiarmid, Concentration, in Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms Combination, vol. 16 (Springer, Berlin, 1998), pp. 195–248
25.
A. Natarajan, Y. Wu, Computational complexity of certifying restricted isometry property, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX, pp. 371–380 (2014)
26.
D. Needell, J.A. Tropp, CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Commun. ACM 53 (12), 93–100 (2010)CrossRefMATH
27.
J. Nelson, E. Price, M. Wootters, New constructions of RIP matrices with fast multiplication and fewer rows, in Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1515–1528 (2014)
28.
D.G. Nishimura, Principles of Magnetic Resonance Imaging (Stanford University, Stanford, CA, 2010)
29.
H. Rauhut, Compressive sensing and structured random matrices, in Theoretical Foundations and Numerical Methods for Sparse Recovery, vol. 9, ed. by M. Fornasier (De Gruyter, Berlin, 2010), pp. 1–92
30.
M. Rudelson, R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements. Commun. Pure Appl. Math. 61 (8), 1025–1045 (2008). Preliminary version in CISS’06
31.
A.M. Tillmann, M.E. Pfetsch, The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing. IEEE Trans. Inform. Theory 60 (2), 1248–1259 (2014)MathSciNetCrossRef
32.
S. Wenger, S. Darabi, P. Sen, K. Glassmeier, M.A. Magnor, Compressed sensing for aperture synthesis imaging, in Proceedings of the International Conference on Image Processing, ICIP, pp. 1381–1384 (2010)
33.
M. Wootters, On the list decodability of random linear codes with large error rates, in Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC, pp. 853–860 (2013)
Metadata
Title
The Restricted Isometry Property of Subsampled Fourier Matrices
Authors
Ishay Haviv
Oded Regev
Copyright Year
2017
Book
Geometric Aspects of Functional Analysis

Print ISBN: 978-3-319-45281-4

Electronic ISBN: 978-3-319-45282-1

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-45282-1_11

Premium Partner

    Image Credits