Sparse recovery with coherent frames via \(\ell_{1-2}\)-analysis (Q6591729)

In signal theory, compressed sensing (CS, in short) proposes to acquire a signal \(\mathbf{x}\in \mathbb{R}^{n}\) by decoding \(m\) linear measurements \(\mathbf{y}= A\mathbf{x}\)+\( \epsilon\), where \(A\in \mathbb{R}^{m\times n}\) is a sensing matrix with \(m\) smaller than \(n\) by one or several orders of magnitude and \(\epsilon\) is an error term modeling measurement errors. The CS theory states that if the unknown signal \(\mathbf{x}\) is sparse (either reasonably or approximately), then under suitable conditions on \(A\) you can recover \(\mathbf{x}\). Among them, we point out the restricted isometry property (see [\textit{E. J. Candès} and \textit{T. Tao}, IEEE Trans. Inf. Theory 51, No. 12, 4203--4215 (2005; Zbl 1264.94121)]) and the null space property. In [\textit{E. J. Candès} et al., Appl. Comput. Harmon. Anal. 31, No. 1, 59--73 (2011; Zbl 1215.94026)], novel results concerning the recovering of signals from undersampled data where such signals are not sparse in an orthonormal basis or incoherent dictionary, but in a truly redundant dictionary, are presented. The CS is viable in this framework as well as the accurate recovery by using the so called \(l_{1}\)-analysis based on a minimization problem in terms of a tight frame. Let us remind that a matrix \(D\in \mathbb{R}^{n\times d}\) with column vectors \(D_{j}, j=1,2, \dots, d\), is a tight frame if \(\|\mathbf{x}\|_{2} ^{2}= \sum_{j=1}^{d} |\langle \mathbf{x}, D_{j} \rangle|^2\) for every \(\mathbf{x} \in \mathbb{R}^{n}\).\N\NIn the paper under review a non convex \(l_{1-2}\) analysis model is introduced for \(A\in \mathbb{R}^{m\times n}\), a measurement matrix, and \(D\), a tight frame, in the sense that you deal with the minimization problem\N\(\min_{\mathbf{x}}\{ \|D^{*} \mathbf{x}\|_{1} - \|D^{*} \mathbf{x}\|_{2}, A\mathbf{x}= \mathbf{y}\}\).\N\NAs a non convex model it is well known that its global minimizer and local minimizer are usually inconsistent. The authors provide a type of null space property characterization which yields necessary and sufficient conditions for the measurement matrix \(A\) such that a vector \(A\mathbf{x}\) can be recovered with a tight frame \(D\) via \(l_{1-2}\)-analysis local minimization or any vector \(\mathbf{x}\) can be uniformly recovered from \(A\mathbf{x}\) with a tight frame \(D\) via \(l_{1-2}\)-analysis minimization locally and globally. \N\NNotice that a vector \(\mathbf{x}\in \mathbb{R}^{n}\) is said to be recovered from \(A\mathbf{x}\) with a tight frame \(D\) via \(l_{1-2}\)-analysis global minimization if \(\mathbf{x}= \operatorname{arg} \{ \|D^{*} \mathbf{z}\|_{1} - \|D^{*} \mathbf{z}\|_{2}: A\mathbf{z}= A\mathbf{x}\}\). On the other hand, a vector \(\mathbf{x}\in \mathbb{R}^{n}\) can be recovered from \(A\mathbf{x}\) with a frame \(D\) via \(l_{1-2}\)-analysis local minimization if there exists \(r(\mathbf{x}) >0\) such that \(\mathbf{x}= \operatorname{arg} \{ \|D^{*} \mathbf{z}\|_{1} - \|D^{*} \mathbf{z}\|_{2}: A\mathbf{z}= A\mathbf{x}, \|\mathbf{z} - \mathbf{x}\|_{2} < r(\mathbf{x})\}\).