Recovery thresholds for l1 optimization in binary compressed sensing

Recently, [3], [7] theoretically analyzed the success of a polynomial l(1) optimization algorithm in solving an under-determined system of linear equations. In a large dimensional and statistical context [3], [7] 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 l(1) optimization succeeds in solving the system. In this paper, we consider the same problem while additionally assuming that all non-zero elements elements are equal to each other. We provide a performance analysis of a slightly modified l(1) optimization. As expected, the obtained recoverable sparsity proportionality constants improve on the equivalent ones that can be obtained if no information about the non-zero elements is available. In addition, we conducted a sequence of numerical experiments and observed that the obtained theoretical proportionality constants are in a solid agreement with the ones obtained experimentally.