A smoothed analysis approach to ℓ1 optimization in compressed sensing

Recently, theoretically analyzed the success of a polynomial ℓ₁-optimization algorithm in solving an under-determined system of linear equations. In a large dimensional and statistical context proved that if the number of equations (measurements in the compressed sensing terminology) in the system is proportional to the length of the unknown vector then there is a sparsity (number of non-zero elements of the unknown vector) also proportional to the length of the unknown vector such that ℓ₁-optimization succeeds in solving the system. In this paper, we consider an alternative performance analysis of ℓ₁-optimization and demonstrate that linear sparsity is recoverable for a large class of almost deterministic measurement matrices.