2011

Full Spark Frames

Alexeev, Boris, Cahill, Jameson, Mixon, Dustin G.

Understand

Finite frame theory has a number of real-world applications.

In applications like sparse signal processing, data transmission with robustness to erasures, and reconstruction without phase, there is a pressing need for deterministic constructions of frames with the following property: every size-M subcollection of the M-dimensional frame elements is a spanning set.
Such frames are called full spark frames, and this paper provides new constructions using the discrete Fourier transform.
Later, we prove that full spark Parseval frames are dense in the entire set of Parseval frames, meaning full spark frames are abundant, even if one imposes an additional tightness constraint.

Built on

Hall, P.: On Representatives of Subsets, J. London Math. Soc. 10
1935
Earlier work this paper cites.
Piff, M.J., Welsh, D.J.A.: On the vector representation of matroids, J. London Math. Soc. 2
1970
Earlier work this paper cites.
Karp, R.M.: Reducibility Among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (Eds.), Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)
1972
Earlier work this paper cites.
Evans, R.J., Isaacs, I.M.: Generalized Vandermonde determinants and roots of prime order, Proc. Amer. Math. Soc. 58
1977
Earlier work this paper cites.
Hartshorne, R.: Algebraic Geometry. Graduate Texts in Mathematics, Springer, New York (1977)
1977
Earlier work this paper cites.
Nakamura, S., Masson, G.M.: Lower bounds on crosspoints in concentrators, IEEE Trans. Comput. C-31
1982
Earlier work this paper cites.
McCormick, S.T.: A Combinatorial Approach to Some Sparse Matrix Problems. Ph.D. Thesis, Stanford University (1983)
1983
Earlier work this paper cites.
Valiant, L., Vazirani, V.: NP is as easy as detecting unique solutions, Theor. Comput. Sci. 47
1986
Earlier work this paper cites.
Stevenhagen, P., Lenstra, H.W.: Chebotarëv and his density theorem, Math. Intelligencer 18
1996
Earlier work this paper cites.
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
1997
Earlier work this paper cites.
Goyal, V.K.: Beyond Traditional Transform Coding. Ph.D. Thesis, University California, Berkeley (1998)
1998
Earlier work this paper cites.
Zauner, G.: Quantendesigns: Grundzüge einer nichtkommutativen Designtheorie. Ph.D. thesis, University of Vienna (1999)
1999
Earlier work this paper cites.
Rapcsák, T.: On minimization on Stiefel manifolds, Eur. J. Oper. Res. 143
2002
Earlier work this paper cites.
Donoho, D.L., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 \ell^{1} minimization, Proc. Nat. Acad. Sci. 100
2003
Earlier work this paper cites.
Strohmer, T., Heath, R.W.: Grassmannian frames with applications to coding and communication, Appl. Comput. Harmon. Anal. 14
2003
Earlier work this paper cites.
Holmes, R.B., Paulsen, V.I.: Optimal frames for erasures, Linear Algebra Appl. 377
2004
Earlier work this paper cites.

Similar

Renes, J.M., Blume-Kohout, R., Scott, A.J., Caves, C.M.: Symmetric informationally complete quantum measurements, J. Math. Phys. 45
2004
Cited alongside, same era.
Wipf, D.P., Rao, B.D.: Sparse Bayesian learning for basis selection, IEEE Trans. Signal Process. 52
2004
Cited alongside, same era.
Candès, E.J., Tao, T.: Decoding by linear programming, IEEE Trans. Inform. Theory 51
2005
Cited alongside, same era.
Fuchs, J.-J.: Sparsity and uniqueness for some specific under-determined linear systems, Proc. IEEE Int. Conf. Acoust. Speech Signal Process., 729–732 (2005)
2005
Cited alongside, same era.
Püschel, M., Kovačević, J.: Real, tight frames with maximal robustness to erasures, Proc. Data Compr. Conf., 63–72 (2005)
2005
Cited alongside, same era.
Tao, T.: An uncertainty principle for cyclic groups of prime order, Math. Research Letters 12
2005
Cited alongside, same era.
Xia, P., Zhou, S., Giannakis, G.B.: Achieving the Welch bound with difference sets, IEEE Trans. Inform. Theory 51
2005
Cited alongside, same era.
Balan, R., Casazza, P., Edidin, D.: On signal reconstruction without phase, Appl. Comput. Harmon. Anal. 20
2006
Cited alongside, same era.
Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory 52
2006
Cited alongside, same era.
Casazza, P.G., Tremain, J.C.: The Kadison-Singer Problem in mathematics and engineering, Proc. Natl. Acad. Sci. U.S.A. 103
2006
Cited alongside, same era.
Dykema, K., Strawn, N.: Manifold structure of spaces of spherical tight frames, Int. J. Pure Appl. Math. 28
2006
Cited alongside, same era.
Balan, R., Bodmann, B.G., Casazza, P.G., Edidin, D.: Fast algorithms for signal reconstruction without phase, Proc. SPIE, 67011L, 1–9 (2007)
2007
Cited alongside, same era.

Then

Delvaux, S., Van Barel, M.: Rank-deficient submatrices of Fourier matrices, Linear Algebra Appl. 429
2008
Later among the works it cites.
Lu, Y.M., Do, M.N.: A Theory for Sampling Signals From a Union of Subspaces, IEEE Trans. Signal Process. 56
2008
Later among the works it cites.
Rudelson, M., Vershynin, R.: On sparse reconstruction from Fourier and Gaussian measurements, Commun. Pure Appl. Anal. 61
2008
Later among the works it cites.
Strohmer, T.: A note on equiangular tight frames, Linear Algebra Appl. 429
2008
Later among the works it cites.
Tropp, J.A.: On the conditioning of random subdictionaries, Appl. Comput. Harmon. Anal. 25
2008
Later among the works it cites.
Balan, R., Bodmann, B.G., Casazza, P.G., Edidin, D.: Painless reconstruction from magnitudes of frame coefficients, J. Fourier Anal. Appl. 15
2009
Later among the works it cites.
Blumensath, T., Davies, M.E.: Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces, IEEE Trans. Inform. Theory 55
2009
Later among the works it cites.
Marx, D.: A parameterized view on matroid optimization problems, Theor. Comput. Sci. 410
2009
Later among the works it cites.
Mohimani, H., Babaie-Zadeh, M., Jutten, C.: A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed ℓ 0 \ell^{0} Norm, IEEE Trans. Signal Process. 57
2009
Later among the works it cites.
Tang, G., Nehorai, A.: Performance Analysis for Sparse Support Recovery, IEEE Trans. Inform. Theory 56
2010
Later among the works it cites.
Cahill, J., Casazza, P.G., Heinecke, A.: A notion of redundancy for infinite frames, Proc. Sampl. Theory Appl. (2011)
2011
Closest in time.
Casazza, P.G., Heinecke, A., Krahmer, F., Kutyniok, G.: Optimally sparse frames, IEEE Trans. Inform. Theory 57
2011
Closest in time.
Davenport, M.A., Duarte, M.F., Eldar, Y.C., Kutyniok, G.: Introduction to Compressed Sensing. In: Eldar, Y.C., Kutyniok, G. (Eds.), Compressed Sensing: Theory and Applications, Cambridge University Press (2011)
2011
Closest in time.
Fickus, M., Mixon, D.G.: Deterministic matrices with the restricted isometry property, Proc. SPIE (2011)
2011
Closest in time.
Mixon, D.G., Quinn, C., Kiyavash, N., Fickus, M.: Equiangular tight frame fingerprinting codes, Proc. IEEE Int. Conf. Acoust. Speech Signal Process., 1856–1859 (2011)
2011
Closest in time.
Strawn, N.: Finite frame varieties: Nonsingular points, tangent spaces, and explicit local parameterizations, J. Fourier Anal. Appl. 17
2011
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…