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:
Introduction to Finite Frame Theory Read chapter Read first chapter

2013 | OriginalPaper | Chapter

9. Finite Frames for Sparse Signal Processing

Authors : Waheed U. Bajwa, Ali Pezeshki

Published in: Finite Frames

Publisher: Birkhäuser Boston

Log in

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

search-config
loading …

Abstract

Over the last decade, considerable progress has been made toward developing new signal processing methods to manage the deluge of data caused by advances in sensing, imaging, storage, and computing technologies. Most of these methods are based on a simple but fundamental observation: high-dimensional data sets are typically highly redundant and live on low-dimensional manifolds or subspaces. This means that the collected data can often be represented in a sparse or parsimonious way in a suitably selected finite frame. This observation has also led to the development of a new sensing paradigm, called compressed sensing, which shows that high-dimensional data sets can often be reconstructed, with high fidelity, from only a small number of measurements. Finite frames play a central role in the design and analysis of both sparse representations and compressed sensing methods. In this chapter, we highlight this role primarily in the context of compressed sensing for estimation, recovery, support detection, regression, and detection of sparse signals. The recurring theme is that frames with small spectral norm and/or small worst-case coherence, average coherence, or sum coherence are well suited for making measurements of sparse signals.

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 Quantization and Finite Frames
next chapter Finite Frames and Filter Banks
Footnotes
1
The sparse signal processing literature often uses the terms sensing matrix, measurement matrix, and dictionary for the frame Φ in this setting.
 
2
Theorem 9.1 has been stated in [28] using the terminology of spark, instead of the URP. The spark of a frame Φ is defined in [28] as the smallest number of frame elements of Φ that are linearly dependent. In other words, Φ satisfies the URP of order K if and only if spark(Φ)≥K+1.
 
3
Recall, with big-O notation, that f(n)=O(g(n)) if there exist positive C and n 0 such that for all n>n 0, f(n)≤Cg(n). Also, f(n)=Ω(g(n)) if g(n)=O(f(n)), and f(n)=Θ(g(n)) if f(n)=O(g(n)) and g(n)=O(f(n)).
 
4
We point out here that if one is willing to tolerate some bias in the estimate, then the estimation error can be made smaller than \(O(\sqrt{\sigma^{2}K})\); see, e.g., [18, 31].
 
5
Recently Bourgain et al. in [10] have reported a deterministic construction of frames that satisfies the RIP of K=O(N 1/2+δ ). However, the constant δ in there is so small that the scaling can be considered K=O(N 1/2) for all practical purposes.
 
6
Recall the definition of the phase of a number r∈ℂ: \(\operatorname{sgn}(r) = \frac{r}{|r|}\).
 
Literature
1.
IEEE Signal Processing Magazine, special issue on compressive sampling (2008)
2.
Bajwa, W.U., Calderbank, R., Jafarpour, S.: Model selection: two fundamental measures of coherence and their algorithmic significance. In: Proc. IEEE Intl. Symp. Information Theory (ISIT’10), Austin, TX, pp. 1568–1572 (2010) CrossRef
3.
Bajwa, W.U., Calderbank, R., Jafarpour, S.: Why Gabor frames? Two fundamental measures of coherence and their role in model selection. J. Commun. Netw. 12(4), 289–307 (2010)
4.
Bajwa, W.U., Calderbank, R., Mixon, D.G.: Two are better than one: fundamental parameters of frame coherence. Appl. Comput. Harmon. Anal. 33(1), 58–78 (2012) MathSciNetMATHCrossRef
5.
Bajwa, W.U., Haupt, J., Raz, G., Nowak, R.: Compressed channel sensing. In: Proc. 42nd Annu. Conf. Information Sciences and Systems (CISS’08), Princeton, NJ, pp. 5–10 (2008) CrossRef
6.
Ben-Haim, Z., Eldar, Y.C., Elad, M.: Coherence-based performance guarantees for estimating a sparse vector under random noise. IEEE Trans. Signal Process. 58(10), 5030–5043 (2010) MathSciNetCrossRef
7.
Blumensath, T., Davies, M.E.: Iterative hard thresholding for compressed sensing. Appl. Comput. Harmon. Anal. 27(3), 265–274 (2009) MathSciNetMATHCrossRef
8.
9.
Boufounos, P., Kutynio, G., Rahut, H.: Sparse recovery from combined fusion frame measurements. IEEE Trans. Inf. Theory 57(6), 3864–3876 (2011) CrossRef
10.
Bourgain, J., Dilworth, S.J., Ford, K., Konyagin, S.V., Kutzarova, D.: Breaking the k 2 barrier for explicit RIP matrices. In: Proc. 43rd Annu. ACM Symp. Theory Computing (STOC’11), San Jose, California, pp. 637–644 (2011)
11.
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) MATH
12.
Bruckstein, A.M., Donoho, D.L., Elad, M.: From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51(1), 34–81 (2009) MathSciNetMATHCrossRef
13.
Calderbank, R., Casazza, P., Heinecke, A., Kutyniok, G., Pezeshki, A.: Sparse fusion frames: existence and construction. Adv. Comput. Math. 35, 1–31 (2011) MathSciNetMATHCrossRef
14.
Candès, E.J.: The restricted isometry property and its implications for compressed sensing. In: C. R. Acad. Sci., Ser. I, Paris, vol. 346, pp. 589–592 (2008)
15.
Candès, E.J., Plan, Y.: Near-ideal model selection by ℓ 1 minimization. Ann. Stat. 37(5A), 2145–2177 (2009) MATHCrossRef
16.
Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory 52(2), 489–509 (2006) MathSciNetMATHCrossRef
17.
Candès, E.J., Tao, T.: Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inform. Theory 52(12), 5406–5425 (2006) MathSciNetCrossRef
18.
Candès, E.J., Tao, T.: The Dantzig selector: statistical estimation when p is much larger than n. Ann. Stat. 35(6), 2313–2351 (2007) MATHCrossRef
19.
Casazza, P., Fickus, M., Mixon, D., Wang, Y., Zhou, Z.: Constructing tight fusion frames. Appl. Comput. Harmon. Anal. 30, 175–187 (2011) MathSciNetMATHCrossRef
20.
Casazza, P., Leon, M.: Existence and construction of finite tight frames. J. Concr. Appl. Math. 4(3), 277–289 (2006) MathSciNetMATH
21.
Casazza, P.G., Kovačević, J.: Equal-norm tight frames with erasures. Appl. Comput. Harmon. Anal. 18(2–4), 387–430 (2003) MATH
22.
Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33–61 (1998) MathSciNetCrossRef
23.
24.
Conway, J.H., Hardin, R.H., Sloane, N.J.A.: Packing lines, planes, etc.: packings in Grassmannian spaces. Exp. Math. 5(2), 139–159 (1996) MathSciNetMATHCrossRef
25.
Dai, W., Milenkovic, O.: Subspace pursuit for compressive sensing signal reconstruction. IEEE Trans. Inform. Theory 55(5), 2230–2249 (2009) MathSciNetCrossRef
26.
Devore, R.A.: Nonlinear approximation. In: Iserles, A. (ed.) Acta Numerica, vol. 7, pp. 51–150. Cambridge University Press, Cambridge (1998)
27.
28.
Donoho, D.L., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization. Proc. Natl. Acad. Sci. 100(5), 2197–2202 (2003) MathSciNetMATHCrossRef
29.
Donoho, D.L., Elad, M., Temlyakov, V.N.: Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Inform. Theory 52(1), 6–18 (2006) MathSciNetCrossRef
30.
Donoho, D.L., Huo, X.: Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inform. Theory 47(7), 2845–2862 (2001) MathSciNetMATHCrossRef
31.
32.
33.
Ehrgott, M.: Multicriteria Optimization, 2nd edn. Springer, Berlin (2005) MATH
34.
Eldar, Y., Kutyniok, G.: Compressed Sensing: Theory and Applications, 1st edn. Cambridge University Press, Cambridge (2012)
35.
Eldar, Y.C., Kuppinger, P., Bölcskei, H.: Block-sparse signals: uncertainty relations and efficient recovery. IEEE Trans. Signal Process. 58(6), 3042–3054 (2010) MathSciNetCrossRef
36.
37.
Fletcher, A.K., Rangan, S., Goyal, V.K.: Necessary and sufficient conditions for sparsity pattern recovery. IEEE Trans. Inform. Theory 55(12), 5758–5772 (2009) MathSciNetCrossRef
38.
39.
Genovese, C.R., Jin, J., Wasserman, L., Yao, Z.: A comparison of the lasso and marginal regression. J. Mach. Learn. Res. 13, 2107–2143 (2012)
40.
Geršgorin, S.A.: Über die Abgrenzung der Eigenwerte einer Matrix. Izv. Akad. Nauk SSSR Ser. Fiz.-Mat. 6, 749–754 (1931)
41.
Gorodnitsky, I.F., Rao, B.D.: Sparse signal reconstruction from limited data using FOCUSS: a re-weighted minimum norm algorithm. IEEE Trans. Signal Process. 45(3), 600–616 (1997) CrossRef
42.
Gribonval, R., Nielsen, M.: Sparse representations in unions of bases. IEEE Trans. Inform. Theory 49(12), 3320–3325 (2003) MathSciNetCrossRef
43.
44.
Haupt, J., Bajwa, W.U., Raz, G., Nowak, R.: Toeplitz compressed sensing matrices with applications to sparse channel estimation. IEEE Trans. Inform. Theory 56(11), 5862–5875 (2010) MathSciNetCrossRef
45.
Haupt, J., Nowak, R.: Compressive sampling for signal detection. In: Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), vol. 3, pp. III-1509–III-1512 (2007)
46.
47.
Hsu, D., Kakade, S., Langford, J., Zhang, T.: Multi-label prediction via compressed sensing. In: Advances in Neural Information Processing Systems, pp. 772–780 (2009)
48.
49.
Kutyniok, G., Pezeshki, A., Calderbank, R., Liu, T.: Robust dimension reduction, fusion frames, and Grassmannian packings. Appl. Comput. Harmon. Anal. 26(1), 64–76 (2009) MathSciNetMATHCrossRef
50.
Lancaster, P., Tismenetsky, M.: The Theory of Matrices, 2nd edn. Academic Press, Orlando (1985) MATH
51.
Mallat, S.G., Zhang, Z.: Matching pursuits with time-frequency dictionaries. IEEE Trans. Signal Process. 41(12), 3397–3415 (1993) MATHCrossRef
52.
53.
Meinshausen, N., Bühlmann, P.: High-dimensional graphs and variable selection with the Lasso. Ann. Stat. 34(3), 1436–1462 (2006) MATHCrossRef
54.
55.
Needell, D., Tropp, J.A.: CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmon. Anal. 26(3), 301–321 (2009) MathSciNetMATHCrossRef
56.
Paredes, J., Wang, Z., Arce, G., Sadler, B.: Compressive matched subspace detection. In: Proc. 17th European Signal Processing Conference, Glasgow, Scotland, pp. 120–124 (2009)
57.
Reeves, G., Gastpar, M.: A note on optimal support recovery in compressed sensing. In: Proc. 43rd Asilomar Conf. Signals, Systems and Computers, Pacific Grove, CA (2009)
58.
59.
Santosa, F., Symes, W.W.: Linear inversion of band-limited reflection seismograms. SIAM J. Sci. Statist. Comput. 7(4), 1307–1330 (1986) MathSciNetMATHCrossRef
60.
Scharf, L.L.: Statistical Signal Processing. Addison-Wesley, Cambridge (1991) MATH
61.
Schnass, K., Vandergheynst, P.: Average performance analysis for thresholding. IEEE Signal Process. Lett. 14(11), 828–831 (2007) CrossRef
62.
Stojnic, M., Parvaresh, F., Hassibi, B.: On the representation of block-sparse signals with an optimal number of measurements. IEEE Trans. Signal Process. 57(8), 3075–3085 (2009) MathSciNetCrossRef
63.
64.
Strohmer, T., Heath, R.W. Jr.: Grassmannian frames with applications to coding and communication. Appl. Comput. Harmon. Anal. 14(3), 257–275 (2003) MathSciNetMATHCrossRef
65.
Sustik, M., Tropp, J.A., Dhillon, I.S., Heath, R.W. Jr.: On the existence of equiangular tight frames. Linear Algebra Appl. 426(2–3), 619–635 (2007) MathSciNetMATHCrossRef
66.
Tibshirani, R.: Regression shrinkage and selection via the Lasso. J. R. Stat. Soc. Ser. B 58(1), 267–288 (1996) MathSciNetMATH
67.
Tropp, J., Gilbert, A., Muthukrishnan, S., Strauss, M.: Improved sparse approximation over quasiincoherent dictionaries. In: Proc. IEEE Conf. Image Processing (ICIP’03), pp. 37–40 (2003)
68.
Tropp, J.A.: Greed is good: algorithmic results for sparse approximation. IEEE Trans. Inform. Theory 50(10), 2231–2242 (2004) MathSciNetCrossRef
69.
Tropp, J.A.: Just relax: convex programming methods for identifying sparse signals in noise. IEEE Trans. Inform. Theory 52(3), 1030–1051 (2006) MathSciNetCrossRef
70.
Tropp, J.A.: Norms of random submatrices and sparse approximation. In: C. R. Acad. Sci., Ser. I, Paris, vol. 346, pp. 1271–1274 (2008)
71.
72.
Tropp, J.A., Wright, S.J.: Computational methods for sparse solution of linear inverse problems. Proc. IEEE 98(5), 948–958 (2010) CrossRef
73.
Wainwright, M.J.: Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1-constrained quadratic programming (Lasso). IEEE Trans. Inform. Theory 55(5), 2183–2202 (2009) MathSciNetCrossRef
74.
Wang, Z., Arce, G., Sadler, B.: Subspace compressive detection for sparse signals. In: IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP), pp. 3873–3876 (2008)
75.
76.
Zahedi, R., Pezeshki, A., Chong, E.K.P.: Robust measurement design for detecting sparse signals: equiangular uniform tight frames and Grassmannian packings. In: Proc. 2010 American Control Conference (ACC), Baltimore, MD (2010)
77.
78.
Zelnik-Manor, L., Rosenblum, K., Eldar, Y.C.: Sensing matrix optimization for block-sparse decoding. IEEE Trans. Signal Process. 59(9), 4300–4312 (2011) MathSciNetCrossRef
79.
Zhao, P., Yu, B.: On model selection consistency of Lasso. J. Mach. Learn. Res. 7, 2541–2563 (2006) MathSciNetMATH
Metadata
Title
Finite Frames for Sparse Signal Processing
Authors
Waheed U. Bajwa
Ali Pezeshki
Copyright Year
2013
Publisher
Birkhäuser Boston
Book
Finite Frames

Print ISBN: 978-0-8176-8372-6

Electronic ISBN: 978-0-8176-8373-3

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-0-8176-8373-3_9

Premium Partner

    Image Credits