Non-Convex Methods for Compressed Sensing and Low-Rank Matrix Problems

In this thesis we study functionals of the type \( \mathcal{K}_{f,A,\b}(\x)= \mathcal{Q}(f)(\x) + \|A\x - \b \| ^2 \), where \(A\) is a linear map, \(\b\) a measurements vector and \( \mathcal{Q} \) is a functional transform called \emph{quadratic envelope}; this object is a very close relative of the \emph{Lasry-Lions envelope} and its use is meant to regularize the functionals \(f\). Carlsson and Olsson investigated in earlier works the connections between the functionals \( \mathcal{K}_{f,A,\b}\) and their unregularized counterparts \(f(\x) + \|A\x - \b \| ^2 \). For certain choices of \(f\) the penalty \( \mathcal{Q}(f)(\cdot)\) acts as sparsifying agent and the minimization of \( \mathcal{K}_{f,A,\b}(\x) \) delivers sparse solutions to the linear system of equations \( A\x = \b \). We prove existence and uniqueness results of the sparse (or low rank, since the functional \(f\) can have any Hilbert space as domain) global minimizer of \( \mathcal{K}_{f,A,\b}(\x) \) for some instances of \(f\), under Restricted Isometry Property conditions on \(A\). The theory is complemented with robustness results and a wide range of numerical experiments, both synthetic and from real world problems.