Typical l(1)-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices
2012 (English)In: Journal of Statistical Mechanics: Theory and Experiment, ISSN 1742-5468, Vol. 2012, no 12, P12003- p.Article in journal (Refereed) Published
We consider the problem of recovering an N-dimensional sparse vector x from its linear transformation y = Dx of M (<N) dimensions. Minimization of the l(1)-norm of x under the constraint y = Dx is a standard approach for the recovery problem, and earlier studies report that the critical condition for typically successful l(1)-recovery is universal over a variety of randomly constructed matrices D. To examine the extent of the universality, we focus on the case in which D is provided by concatenating T = N/M matrices O-1, O-2,O- ... ,O-T drawn uniformly according to the Haar measure on the M x M orthogonal matrices. By using the replica method in conjunction with the development of an integral formula to handle the random orthogonal matrices, we show that the concatenated matrices can result in better recovery performance than that predicted by the universality when the density of non-zero signals is not uniform among the T matrix modules. The universal condition is reproduced for the special case of uniform non-zero signal densities. Extensive numerical experiments support the theoretical predictions.
Place, publisher, year, edition, pages
2012. Vol. 2012, no 12, P12003- p.
source and channel coding, error correcting codes, statistical inference
Signal Processing Condensed Matter Physics
IdentifiersURN: urn:nbn:se:kth:diva-107207DOI: 10.1088/1742-5468/2012/12/P12003ISI: 000312963100004ScopusID: 2-s2.0-84871207413OAI: oai:DiVA.org:kth-107207DiVA: diva2:575281
FunderSwedish Research Council, 621-2011-1024ICT - The Next Generation
QC 201301102012-12-092012-12-092013-04-11Bibliographically approved