Mean breakdown points for compressed sensing by uniformly distributed matrices

• Ashino Ryuichi

  Division of Mathematical Sciences, Osaka Kyoiku University

• Vaillancourt Rémi

  Department of Mathematics and Statistics, University of Ottawa

抄録

It is graphically observed that curves of mean breakdown points obtained by $\ell_1$ optimization for compressed sensing defined by underdetermined systems $y=Aw$ with uniformly distributed random matrices $A\in{\mathbb R}^{d\times m}$ and sparse $w$ almost coincide with the curves obtained by normally distributed random matrices, both with sparse vectors $w^+$ with nonnegative components and $w^\pm$ with components of either sign. Three-dimensional figures illustrate asymptotic phase transition cliffs. These and the standard deviation of the mean breakdown points can be used to define a level of sparseness of $w$ below which a unique solution is expected to a high probability.

収録刊行物

• JSIAM Letters

  JSIAM Letters 2 (0), 111-114, 2010

  一般社団法人 日本応用数理学会

キーワード

• phase transition
• compressed sensing
• $\ell_1$ linear programming
• sparse solution of underdetermined system
• mean breakdown points

詳細情報

• CRID: 1390282680278438144
• NII論文ID: 130000433683
• DOI: 10.14495/jsiaml.2.111
• ISSN: 18830617
• ISSN: 18830609
• Web Site: https://www.jstage.jst.go.jp/article/jsiaml/2/0/2_0_111/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可