Full Spark Frames

被引:87
作者
Alexeev, Boris [2 ]
Cahill, Jameson [3 ]
Mixon, Dustin G. [1 ]
机构
[1] Princeton Univ, Program Appl & Computat Math, Princeton, NJ 08544 USA
[2] Princeton Univ, Dept Math, Princeton, NJ 08544 USA
[3] Univ Missouri, Dept Math, Columbia, MO 65211 USA
关键词
Frames; Spark; Sparsity; Erasures; SIGNAL RECONSTRUCTION; TIGHT FRAMES; REPRESENTATION; SPARSITY; FOURIER; UNION;
D O I
10.1007/s00041-012-9235-4
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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. Finally, we prove that testing whether a given matrix is full spark is hard for NP under randomized polynomial-time reductions, indicating that deterministic full spark constructions are particularly significant because they guarantee a property which is otherwise difficult to check.
引用
收藏
页码:1167 / 1194
页数:28
相关论文
共 51 条
[31]  
MCCORMICK S. T., 1983, Ph.D. thesis
[32]  
Mixon DG, 2011, INT CONF ACOUST SPEE, P1856
[33]   A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed l0 Norm [J].
Mohimani, Hosein ;
Babaie-Zadeh, Massoud ;
Jutten, Christian .
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2009, 57 (01) :289-301
[34]  
NAKAMURA S, 1982, IEEE T COMPUT, V31, P1173, DOI 10.1109/TC.1982.1675941
[35]   ON VECTOR REPRESENTATION OF MATROIDS [J].
PIFF, MJ ;
WELSH, DJA .
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY, 1970, 2 (06) :284-&
[36]  
Püschel M, 2005, IEEE DATA COMPR CONF, P63
[37]   On minimization on Stiefel manifolds [J].
Rapcsák, T .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 143 (02) :365-376
[38]   Symmetric informationally complete quantum measurements [J].
Renes, JM ;
Blume-Kohout, R ;
Scott, AJ ;
Caves, CM .
JOURNAL OF MATHEMATICAL PHYSICS, 2004, 45 (06) :2171-2180
[39]   Equiangular tight frames from Paley tournaments [J].
Renes, Joseph M. .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 426 (2-3) :497-501
[40]   On sparse reconstruction from Fourier and Gaussian measurements [J].
Rudelson, Mark ;
Vershynin, Roman .
COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 2008, 61 (08) :1025-1045