Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Typical l(1)-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices
Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology.
KTH, School of Electrical Engineering (EES), Communication Theory. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
KTH, School of Electrical Engineering (EES), Communication Theory. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0003-2638-6047
2012 (English)In: Journal of Statistical Mechanics: Theory and Experiment, ISSN 1742-5468, E-ISSN 1742-5468, Vol. 2012, no 12, P12003- p.Article in journal (Refereed) Published
Abstract [en]

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.
Keyword [en]
source and channel coding, error correcting codes, statistical inference
National Category
Signal Processing Condensed Matter Physics
Identifiers
URN: urn:nbn:se:kth:diva-107207DOI: 10.1088/1742-5468/2012/12/P12003ISI: 000312963100004Scopus ID: 2-s2.0-84871207413OAI: oai:DiVA.org:kth-107207DiVA: diva2:575281
Funder
Swedish Research Council, 621-2011-1024ICT - The Next Generation
Note

QC 20130110

Available from: 2012-12-09 Created: 2012-12-09 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Chatterjee, Saikat

Search in DiVA

By author/editor
Vehkaperä, MikkoChatterjee, Saikat
By organisation
Communication TheoryACCESS Linnaeus Centre
In the same journal
Journal of Statistical Mechanics: Theory and Experiment
Signal ProcessingCondensed Matter Physics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 69 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf