Abstract | ||
---|---|---|
The sparse representation problem of recovering an N dimensional sparse vector x from M <; N linear observations y = Dx given dictionary D is considered. The standard approach is to let the elements of the dictionary be independent and identically distributed (IID) zero-mean Gaussian and minimize the l1-norm of x under the constraint y = Dx. In this paper, the performance of l1-reconstruction is analyzed, when the dictionary is bi-orthogonal D = [O1 O2], where O1, O2 are independent and drawn uniformly according to the Haar measure on the group of orthogonal M × M matrices. By an application of the replica method, we obtain the critical conditions under which perfect l1-recovery is possible with bi-orthogonal dictionaries. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1109/ITW.2012.6404757 | Information Theory Workshop |
Keywords | DocType | Volume |
computational complexity,convex programming,matrix algebra,minimisation,Haar measure,N dimensional sparse vector,N linear observations,biorthogonal dictionaries,convex relaxation method,independent-and-identically distributed zero-mean Gaussian,l1-norm minimization,nonpolynomial hard problem,orthogonal M × M matrices,replica method,sparse representation problem | Journal | abs/1204.4065 |
ISBN | Citations | PageRank |
978-1-4673-0222-7 | 1 | 0.36 |
References | Authors | |
7 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
M. Vehkapera | 1 | 148 | 10.87 |
Yoshiyuki Kabashima | 2 | 136 | 27.83 |
Saikat Chatterjee | 3 | 320 | 40.34 |
E. Aurell | 4 | 1 | 0.36 |