  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 of 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.
