An Error Bound of Signal Recovery for Penalized Programs in Linear Inverse Problems

Penalized programs are widely used to solve linear inverse problems in the presence of noise. For now, the study of the performance of panelized programs has two disadvantages. First, the results have some limitations on the tradeoff parameters. Second, the effect of the direction of the noise is not clear. This paper studies the performance of penalized programs when bounded noise is presented. A geometry condition which is used to study the noise-free problems and constrained problems is provided. Under this condition, an explicit error bound which guarantees stable recovery (i.e., the recovery error is bounded by the observation noise up to some constant factor) is proposed. The results are different from many previous studies in two folds. First, the results provide an explicit bound for all positive tradeoff parameters, while many previous studies require that the tradeoff parameter is sufficiently large. Second, the results clear the role of the direction of the observation noise playing in the recovery error, and reveal the relationship between the optimal tradeoff parameters and the noise direction. Furthermore, if the sensing matrix has independent standard normal entries, the above geometry condition can be studied using Gaussian process theory, and the measurement number needed to guarantee stable recovery with high probability is obtained. Simulations are provided to verify the theoretical results.