线性等式与不等式组稀疏解的唯一性条件

Uniqueness conditions for the sparsest solution of linear systems

近年来,稀疏优化广泛应用在信号处理、机器学习、图像去噪和计算机视觉等方面,得到了深入的研究和快速的发展.本文考虑含有一般线性等式和不等式约束的广义l_(0-)最小化问题.尽管l_(0-)最小化问题是NP-困难的,但已有多种计算方法可以用来克服这一计算上的困难,其中一种常用的方法是,通过一个凸优化问题来近似求解原问题.具体地,用l_(1-)范数代替l_(0-)范数得到l_(0-)最小化问题的一个凸松弛.在这类方法中,研究什么条件可以保证两个问题等价是非常重要的.基于值域空间性质(RSP)的分析方法,本文提出广义l_(0-)最小化问题的RSP性质,并且证明在某些条件下,RSP性质可以保证l_(0-)最小化问题与它的凸松弛l_(1-)最小化问题是等价的.最后,本文对所使用的条件给出一些说明.

Sparse optimization has attracted extensive attention and has developed rapidly in recent years with a range of applications including signal processing, machine learning, image inpainting and computer vision. In this paper, we consider a general l_（0-）minimization problem with linear constraints. Unfortunately, l_（0-）minimization problem is NP-hard in general, but several algorithmic approaches, especially l_（1-）minimization which replaces l_（0-）norm by l_（1-）norm, are applied to overcome the computational bottleneck. Accordingly, as l_（1-）minimization can be regarded as a heuristic to l_（0-）minimization, it is of great importance to figure out what conditions can guarantee the equivalence between the two problems. Based on the methodology of the range space property（RSP） analysis, we propose the corresponding RSP conditions for the concerned problem and use RSP to prove that l_（0-）minimization problem is equivalent to its heuristic l_（1-）minimization under some conditions. In addition, we point out that these conditions can be met for many classes of problems.