2016/08/30 by Lange, Jan-Hendrik, Pfetsch, Marc E., Seib, Bianca M. +1
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1608.08678
We investigate conditions for the unique recoverability of sparse integer-valued signals from a small number of linear measurements. Both the objective of minimizing the number of nonzero components, the so-called ℓ0-norm, as well as its popular substitute, the ℓ1-norm, are covered. Furthermore, integrality constraints and possible bounds on the variables are investigated. Our results show that the additional prior knowledge of signal integrality allows for recovering more signals than what can be guaranteed by the established recovery conditions from (continuous) compressed sensing. Moreover, even though the considered problems are \NP-hard in general (even with an ℓ1-objective), we investigate testing the ℓ0-recovery conditions via some numerical experiments. It turns out that the corresponding problems are quite hard to solve in practice using black-box software. However, medium-sized instances of ℓ0- and ℓ1-minimization with binary variables can be solved exactly within reasonable time.