TY - JOUR

T1 - Optimally sparse frames

AU - Casazza, Peter G.

AU - Heinecke, Andreas

AU - Krahmer, Felix

AU - Kutyniok, Gitta

N1 - Funding Information:
Manuscript received September 03, 2010; revised March 18, 2011; accepted June 08, 2011. Date of current version November 11, 2011. Part of this work was completed while A. Heinecke visited the Institute of Mathematics at the University of Osnabrück. P. G. Casazza and A. Heinecke were supported by the grants AFOSR F1ATA00183G003, NSF 1008183, and DTRA/NSF 1042701. A. Hei-necke and F. Krahmer were supported in part by the Institute of Advanced Study through the Park City Math Institute, where part of this work was completed. F. Krahmer was also supported by the Hausdorff Center for Mathematics. G. Kutyniok was supported by the DFG Grant SPP-1324, KU 1446/13, and DFG Grant KU 1446/14.

PY - 2011/11

Y1 - 2011/11

N2 - Frames have established themselves as a means to derive redundant, yet stable decompositions of a signal for analysis or transmission, while also promoting sparse expansions. However, when the signal dimension is large, the computation of the frame measurements of a signal typically requires a large number of additions and multiplications, and this makes a frame decomposition intractable in applications with limited computing budget. To address this problem, in this paper, we focus on frames in finite-dimensional Hilbert spaces and introduce sparsity for such frames as a new paradigm. In our terminology, a sparse frame is a frame whose elements have a sparse representation in an orthonormal basis, thereby enabling low-complexity frame decompositions. To introduce a precise meaning of optimality, we take the sum of the numbers of vectors needed from this orthonormal basis when expanding each frame vector as sparsity measure. We then analyze the recently introduced algorithm Spectral Tetris for construction of unit norm tight frames and prove that the tight frames generated by this algorithm are in fact optimally sparse with respect to the standard unit vector basis. Finally, we show that even the generalization of Spectral Tetris for the construction of unit norm frames associated with a given frame operator produces optimally sparse frames.

AB - Frames have established themselves as a means to derive redundant, yet stable decompositions of a signal for analysis or transmission, while also promoting sparse expansions. However, when the signal dimension is large, the computation of the frame measurements of a signal typically requires a large number of additions and multiplications, and this makes a frame decomposition intractable in applications with limited computing budget. To address this problem, in this paper, we focus on frames in finite-dimensional Hilbert spaces and introduce sparsity for such frames as a new paradigm. In our terminology, a sparse frame is a frame whose elements have a sparse representation in an orthonormal basis, thereby enabling low-complexity frame decompositions. To introduce a precise meaning of optimality, we take the sum of the numbers of vectors needed from this orthonormal basis when expanding each frame vector as sparsity measure. We then analyze the recently introduced algorithm Spectral Tetris for construction of unit norm tight frames and prove that the tight frames generated by this algorithm are in fact optimally sparse with respect to the standard unit vector basis. Finally, we show that even the generalization of Spectral Tetris for the construction of unit norm frames associated with a given frame operator produces optimally sparse frames.

KW - Computational complexity

KW - frame decompositions

KW - frame operator

KW - frames

KW - redundancy

KW - sparse approximations

KW - sparse matrices

KW - tight frames

UR - http://www.scopus.com/inward/record.url?scp=81255143118&partnerID=8YFLogxK

U2 - 10.1109/TIT.2011.2160521

DO - 10.1109/TIT.2011.2160521

M3 - Article

AN - SCOPUS:81255143118

SN - 0018-9448

VL - 57

SP - 7279

EP - 7287

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 11

M1 - 5929561

ER -