A numerical exploration of compressed sampling recovery

Fadili, Jalal; Peyré, Gabriel; Dossal, Charles

Fadili, Jalal; Peyré, Gabriel; Dossal, Charles (2010), A numerical exploration of compressed sampling recovery, Linear Algebra and its Applications, 432, 7, p. 1663-1679. http://dx.doi.org/10.1016/j.laa.2009.11.022

Type

Article accepté pour publication ou publié

External document link

http://hal.archives-ouvertes.fr/hal-00402455/en/

Date

2010

Journal name

Linear Algebra and its Applications

Volume

432

Number

Publisher

Elsevier

Pages

1663-1679

Abstract (EN)

This paper explores numerically the efficiency of ℓ1 minimization for the recovery of sparse signals from compressed sampling measurements in the noiseless case. This numerical exploration is driven by a new greedy pursuit algorithm that computes sparse vectors that are difficult to recover by ℓ1 minimization. The supports of these pathological vectors are also used to select sub-matrices that are ill-conditioned. This allows us to challenge theoretical identifiability criteria based on polytopes analysis and on restricted isometry conditions. We evaluate numerically the theoretical analysis without resorting to Monte-Carlo sampling, which tends to avoid worst case scenarios.

Subjects / Keywords

Compressed sensing; Restricted isometry constant; Polytopes; ℓ1 minimization