text:
\begin{document}
\maketitle
\begin{abstract}
In compressed sensing a sparse vector is approximately retrieved from an under-determined equation system $Ax=b$. Exact retrieval would mean solving a large combinatorial problem which is well known to be NP-hard. For $b$ of the form $Ax_0+\ep$ where $x_0$ and $\ep$ is noise, the ``oracle solution'' is the one you get if you a priori know the support of $x_0$, and is the best solution one could hope for. We provide a non-convex functional whose global minimum is the oracle solution, with the property that any other local minimizer necessarily has high cardinality. We provide estimates of the type
$\|\hat x-x_0\|_2\leq C\|\ep\|_2$ with constants $C$ that are significantly lower than for competing methods or theorems, and our theory relies on soft assumptions on the matrix $A$, in comparison with standard results in the field.

The framework also allows to incorporate a priori information on the cardinality of the sought vector. In this case we show that despite being non-convex, our cost functional has no spurious local minima and the global minima is again the oracle solution, thereby providing the first method which is guaranteed to find this point for reasonable levels of noise, without resorting to combinatorial methods.

{\bf Keywords:}\textit{compressed sensing, regularization, non-convex/non-smooth optimization}
{\bf MSC2010:}{49J25, 49M20, 65K10, 90C26, 90C27}

\end{abstract}

\section{Introduction}\label{sec:intro}
\subsection{Background}

We consider the classical compressed sensing problem of minimizing the cardinality $\card(x)$ of an approximate solution to an underdetermined equation system $Ax=b$, i.e. \begin{equation}\label{l0prob}\argmin_{x:~\|Ax-b\|_2<\varepsilon}\card(x),
\end{equation} where $\varepsilon>0$
is some allowed tolerance of the error and $x_0$ lies in $\R^n$ or $\C^n$. Problem \eqref{l0prob} is NP-hard \cite{natarajan1995sparse} and a popular approach, commonly referred to as ``compressed sensing'', is to replace $\card(x)$ with the convex function $\|x\|_1$, i.e. \begin{equation}\label{l1prob}\argmin_{x:~\|Ax-b\|_2<\varepsilon}\|x\|_1.\end{equation} This method goes back (at least) to the 70's (see the introduction of \cite{candes2008enhancing} for a nice historical overview) but received increasing attention in the late 90's due to the work by Chen, Donoho and Saunders \cite{chen2001atomic} on what they called basis pursuit, which amounts to solving
\begin{equation}\label{l1probdual}\argmin\{\lambda\|x\|_1+\frac{1}{2}\|Ax-b\|_2^2\}\end{equation}
for a suitable choice of parameter $\lambda$ (playing the role of $\varepsilon$ in the $\ell^1$-version of \eqref{l0prob}). In fact, \eqref{l1probdual} is the dual problem of \eqref{l1prob} in the sense that for each $\varepsilon$ there is a $\lambda$ such that the solution of \eqref{l1prob} and \eqref{l1probdual} coincides. The method received massive attention after the works of Cand\`{e}s and coworkers in the early 2000, and the term compressed sensing was coined. In \cite{candes2006stable}, Cand\`{e}s, Romberg and Tao proved the surprising result that, given a sparse vector $x_0$ and a measurement
\begin{equation}
\label{nise}b=Ax_0+\ep,
\end{equation}
where $\ep$ is Gaussian noise, solving \eqref{l1prob} yields (for a suitable choice of $\varepsilon$) a vector $\hat x$ that satisfies \begin{equation}\label{crt}
\|\hat x-x_0\|_2<C_K\|\ep\|_2,
\end{equation}
where $C_K$ is a constant. Arguing that it is impossible to beat a linear \begin{wrapfigure}{r}{0.4\textwidth}
  \begin{center}
     \includegraphics[width=.4\textwidth]{penalties.pdf}\\
  \end{center}
 \caption{Illustration of penalties.}
\label{S22card}
\end{wrapfigure} dependence on the noise (even knowing the true support of $x_0$ a priori), the estimate \eqref{crt} led the authors to conclude that ``no other method can significantly outperform this''. The result holds given certain assumptions on the matrix $A$, related to the restricted isometry properties of $A$, which in a separate publication (Theorem 1.6, \cite{candes2005decoding}) was shown to hold with ``overwhelming probability''. The result is indeed surprising, in Figure \ref{S22card} we display the one-dimensional counterparts of $\card (x)$ and $\|x\|_1$, demonstrating that $\card(x)$ and $\|x\|_1$ are indeed quite different functionals.

However, the definition ``overwhelming probability'' is asymptotic in its nature, and therefore it is not clear if \eqref{crt} is valid in a moderately sized application (it often is not, see Section \ref{sec:size}). This continues to be the state of the art, see e.g.~\cite{adcock2016generalized,adcock2017breaking,candes-etal-acm-2011} which provides \textit{asymptotic} theorems about when compressed sensing works in concrete setups. Moreover, whereas very strong recovery results were reported e.g.~in \cite{candes2006robust,chartrand2007exact,donoho2006most} for the case of \textit{exact data} $b=Ax_0$, in the presence of noise (c.f. \eqref{nise}) the method gives a well known bias (see e.g. \cite{fan2001variable,mazumder2011sparsenet}). The $\ell^1$ term not only has the (desired) effect of forcing many entries in $x$ to 0, but also the (undesired) effect of diminishing the size of the non-zero entries. This is clearly visible even in the one-dimensional situation; the function $\R\ni x\mapsto \lambda|x|+\frac{1}{2}|x-x_0|^2$ has its minimum shifted towards 0 from the sought point $x_0$. This has led to a large amount of non-convex suggestions to replace the $\ell^1$-penalty, see e.g. \cite{bredies2015minimization,blumensath2009iterative,blumensath2008iterative,attouch2013convergence,chartrand2007exact,pan2015relaxed,zou2008one,fan2004nonconcave,wang2014optimal,selesnick2017sparse,loh2013regularized,fan2014strong,zhang2012general,zhang2010nearly,loh2017support,candes2008enhancing,breheny2011coordinate,fan2001variable,mazumder2011sparsenet}.

These methods are tailormade for the sparsity problem, and upon changing the non-convex penalty $\card(x)$ it is not clear what to do. We consider now the general problem of minimizing \begin{equation}\label{genprob}
f(x)+\|Ax-b\|_2^2\end{equation} where $f$ is some non-convex penalty and $x$ is a vector in some linear space, not necessarily $\R^n$.

For example, if the desired cardinality $K$ is known a priori, we can take $f$ to be the indicator function $\iota_{P_K}$ of the set $P_K=\{x:\card (x)\leq K\}$ in which case \eqref{genprob} reduces to
\begin{equation}\label{agt1intro}
\argmin_{\card (x)\leq K}\|Ax-b\|.
\end{equation}

\begin{wrapfigure}{r}{0.4\textwidth}
     \includegraphics[width=0.4\textwidth]{quadraticenvelope.pdf}
 \caption{Illustration of a non-convex function $f$ (red) and its quadratic envelope $Q_2(f)$ (black). The black graph lies slightly below for illustration only.}\label{f456}
\end{wrapfigure}

In \cite{carlsson2018convex} the ``quadratic envelope'' $\Q_2(f)$ was introduced, where $\Q_2$ is the ``quadratic biconjugate'' (apart from the name, this transform was introduced already in \cite{carlsson2016convexification}, see Figure \ref{f456} for an illustraion). It has the property that $\Q_2 (f) (x)+\|x\|^2$ is the lower semi-continuous convex envelope of $f(x)+\|x\|^2$, and the relationship between
\begin{equation}\label{genprobS}
\Q_2(f)(x)+\|Ax-b\|_2^2\end{equation}
and the original functional in \eqref{genprob} was investigated. The main result is that, given $\|A\|<1$, the set of local minimizers to \eqref{genprobS} is a subset of the local minimizers of \eqref{genprob}, and most importantly that the global minimizers coincide. In the particular case of $f(x)=\card(x)$ the functional \eqref{genprobS} has previously been introduced by Zhang \cite{zhang2010nearly} under the name MCP (Minimax Concave Penalty) and independently by Aubert, Blanc-Feraud and Soubies \cite{soubies-etal-siims-2015} under the name $CE\ell0$. It also shows up in earlier publications, for example (2.4) in \cite{fan2001variable}, but it seems like \cite{zhang2010nearly} is the first comprehensive performance study and  \cite{soubies-etal-siims-2015} the first publication where the connection with convex envelopes appears. For this choice of $f$, the value of the contributions of the present paper is mainly theoretical, which goes much beyond what was previously known. In particular we show that the global minimizer with the MCP-penalty (i.e.~$\Q_2(\card)$) is the oracle solution (for certain choice of parameters). On the other hand, $\Q_2(\iota_{P_K})$ is a new object that has only appeared previously in earlier publications by the authors of the present article. In this article we provide theoretical results of the type \eqref{crt} for the two concrete functionals $\Q_2(\card)$ and $\Q_2 (\iota_{P_K})$. A more extensive discussion of previous results concerning MCP/$CE\ell0$ is found in Section \ref{review}, as well as other related results on non-convex optimization.

\subsection{Contributions}

A clear drawback with non-convex optimization schemes is that algorithms are bound to get stuck in local minima, and in concrete situations it is hard to determine weather this is the case or not. In the present article we give conditions on $A$ which imply that any local minima of \eqref{genprobS} for $f(x)=\card(x)$ necessarily has a high cardinality unless it is the global minima. Hence, if a sparse local minima is found one can be sure that it is the global minima. In the case of $f=\iota_{P_K}$ we take this one step further and give conditions under which \eqref{genprobS} has a unique local minimizer, which hence must be the global minimizer as well as the solution to the original problem \eqref{agt1intro}.

In the case when $b=Ax_0+\ep$ and $x_0$ is a sparse vector, we significantly improve the state of the art in compressed sensing in a number of ways. Firstly, the conditions on $A$ hold in greater generality. Secondly, we obtain an estimate corresponding to \eqref{crt} where the involved constants are significantly smaller than $C_K$. Thirdly (and most importantly), the method seems to work better in practice, at least in the setting when $A$ has normalized Gaussian random columns. In particular, for reasonable values of noise (e.g.~$SNR\approx 4$ for the case of a 100x200 matrix $A$, see Section \ref{sec:num}) we can find the oracle solution using the Forward Backward Splitting algorithm.

In Section~\ref{sec:mainResults} we present highlights from the theory, show some numerical results and compare with the traditional $\ell^1$-method \eqref{l1probdual}. In \ref{review} we give a brief review of the field. The remainder of the paper, Sections \ref{sec:unique}-\ref{seccardfix}, are devoted to developing the theory.

\section{Summary of Main Results and Innovations}\label{sec:mainResults}

\subsection{Sparse recovery via $\Q_2(\card)$}

We return to the first problem of minimizing \eqref{genprobS} for $f=\card(x)$ i.e.
\begin{equation}\label{q1}\K(x)=\mu \card{(x)}+\|Ax-b\|^2\end{equation} (where we introduce the parameter $\mu$ to control the tradeoff between sparsity and data-fit) which we regularize with \begin{equation}\label{q1reg}\K_{reg}(x)=\Q_2(\mu\card){(x)}+\|Ax-b\|^2.\end{equation} The graph of $\Q_2(\card)$ is depicted in Figure \ref{S22card}. Is it true that unique global minimizers exist (recall that they are the same given $\|A\|<1$)? It is easy to see that this is not the case in general, just consider the case of a $2x4-$matrix $A$ such that every pair of columns are linearly independent, and let $\mu$ be such that the global minimum is attained when $\|Ax-b\|=0$. In this case we have $\binom{4}{2}=6$ choices that all give the global minimum. However, in the above example there exists no ``sparse'' solution, for 2 equals the row-dimension of the matrix, and by sparse we mean a number much smaller than this. For an $m \times n$ matrix $A$, with columns sampled from the unit sphere of $\mathbb{R}^n$, this is formalized in Lemma 2.1 of \cite{donoho2006most}, where it is shown that \eqref{l0prob} with $\varepsilon=0$ has a unique sparse solution (with probability 1) if $b=Ax_0$ and $\supp x_0<m/2$, which is an upper bound of how much sparsity one needs in order to have a well posed sparse problem.

In this paper we will study uniqueness of sparse minimizers of \eqref{q1reg}, in the sense that we give concrete conditions such that if there exists one local minimizer $x'$ of \eqref{q1reg} with the property that $\card(x')<<m$ (in a manner to be made precise), then
\begin{itemize}
\item $x'$ is automatically a global minimizer
\item any other stationary point $x''$ of \eqref{q1reg} satisfies $\card(x'')>>\card(x')$.
\end{itemize}

We remind the reader that $A$ satisfies a Restricted Isometry Property for integer $k$, if any $k$ columns of $A$ behaves approximately as an isometry, in the sense that the resulting matrix can be bounded below by $\sqrt{1-\delta_k}Id$ and bounded above by $\sqrt{1+\delta_k}Id$, where $\delta_k$ is the restricted isometry constant for $k$. Classical results from compressed sensing literature usually require that the numbers $\delta_k$ are small, something which we have found is hard to fulfill in practice. For example, the famous estimate \eqref{crt} holds under the assumption that \begin{equation}\label{ki}\delta_{3K}+3\delta_{4K}<2.\end{equation} Our numerical evaluation (see Section \ref{sec:size}) shows that
 if $K=5$ this condition is usually not satisfied for a Gaussian random matrix $A$ (with normalized columns) of size $m\times n$, unless $m$ is (at least) around 500. The statement that RIP holds with overwhelming probability \cite{candes2005decoding} is therefore somewhat misleading, since it is based on an asymptotic estimate. For a small size matrix of the type discussed above it typically never applies (more on this in Section \ref{sec:size}). That the RIP-conditions are hard to satisfy in practice is well known by the community, and has led to interesting new contributions about efficiency of $\ell^1$ without RIP, given that the problem is sampled in a certain way, see e.g.~\cite{adcock2016generalized,adcock2017breaking}. However, these results are asymptotic in nature and do not apply in as general situation as the ones we will present here.

We base the theory of this paper on the ``Restricted Linear Independence Property'' (RLIP), basically constituting the lower estimate of the RIP. More precisely, we define \begin{equation}\label{beta}\beta_k=\inf\{\frac{\|Ax\|}{\|x\|}:~ x\neq 0,~\card(x)\leq k\}\end{equation} for $k=1\ldots n$. We say that $A$ satisfies RLIP with respect to the property $P_K=\{x:\card(x)\leq K\}$ if $\beta_K\neq 0$. In other words $A$ is RLIP with respect to this property if and only if any $K$ chosen columns of $A$ are linearly independent. The relationship with RIP is as follows; if $A$ satisfies RIP with constant $\delta_k$ then it satisfies RLIP with $\beta_k\geq \sqrt{1-\delta_k}$, whereas the converse often does not hold.

To give an idea of the type of results proven in this paper, we first present two corollaries of theorems in Section \ref{seccard}.
\begin{corollary}\label{cor:globalpoint2}
Let $A$ have normalized columns and let $x'$ be a stationary point of $\K_{reg}$ with $\card(x')=K$ and set $z'=(I-A^* A)x' + A^* b$. Assume that
\begin{equation}\label{cond3c}|z_i'|\not\in\left[{\beta_{2K}^2}{\sqrt{\mu}},\frac{1}{\beta_{2K}^2}{\sqrt{\mu}}\right],\quad 1\leq i\leq n.\end{equation}
If \begin{equation}\label{cond2c}\fro{Ax'-b}< \mu ,\end{equation} then $x'$ is a unique global minimum of both $\K$ and $\K_{reg}$.
Moreover, any other stationary point $x''$ has a larger support. \end{corollary}
The statement is a combination of Theorem \ref{thm:statpoint:vec} and \ref{thm:globalpoint2} (for the choice $N=2K$). Upon assuming a bit more in \eqref{cond3c} and \eqref{cond2c}, we may also conclude that $x''$ has substantially larger support. As a curious remark, note that $\beta_{2K}>0$ forces $m\geq 2K$ which is precisely the upper bound given by Lemma 2.1 in \cite{donoho2006most} mentioned above.

In the case when $b=Ax_0+\ep$, as discussed earlier, we can say more. Below we state Theorem \ref{thm:doctorgadget} for the particular case $N=2K$.

\begin{corollary}\label{cor:doctorgadget}
Suppose that $b=Ax_0+\ep$ and set $\card (x_0)=K.$ Assume that
$\|\ep\|< {\beta_{2K}^2\sqrt{\mu}}$ and $$|x_{0,j}|>\para{\frac{1}{\beta_{2K}^2}+1}\sqrt{\mu},\quad j\in \supp x_0.$$ Then there exists a unique global minimum $x'$ to $\K_{reg}$ as well as $\K$, with the property that $\supp x'=\supp x_0$, that $$\|x'-x_0\|\leq \frac{\|\ep\|}{\beta_K},$$ and that $\card(x'')> K$ for any other stationary point $x''$ of $\K_{reg}$.
\end{corollary}

Note that the conditions on $\ep$ and $x_0$ are very natural; if the noise is too large or if the non-zero entries of $x_0$ are too small, there is no hope of correctly retrieving the support.

\subsection{Known ``model order''.}
We now discuss the situation when the model order, i.e. the amount $K$ of non-zero entries, is known. This problem is also known as the $K$-sparse problem and studied e.g.~in \cite{blumensath2008iterative}. For simplicity we restrict attention to $\R^n$, corresponding results for $\C^n$ are similar but the assumptions on $A$ are slightly more technical. In this case we set
\begin{equation}\label{q2}\K_K(x)=\iota_{P_K}(x)+\|Ax-b\|^2\end{equation} (where the subindex $K$ separates the notation from \eqref{q1}) which we regularize with \begin{equation}\label{q2reg}\K_{K,reg}(x)=\Q_2(\iota_{P_K})(x)+\|Ax-b\|^2.\end{equation} The result corresponding to Corollary \ref{cor:globalpoint2} reads as follows
\begin{corollary}\label{cytwsgdf}
Let $A$ have normalized columns such that no pair is orthogonal, and assume that $n\geq m+K+2$. Any local minimizer $x'$ of $\ksir$ then lies in $P_K$. Moreover, set $z'=(I-A^* A)x' + A^* b$, let $\tilde z'$ contain the elements of $z'$ sorted after decreasing magnitude,
 and assume that
\begin{equation}\label{n}|\tilde z'_{K+1}|<(2\beta_{2K}^2-1)|\tilde z'_{K}|.\end{equation}
Then $x'$ is the unique global minimum of $\ksi$ and $\ksir$.
\end{corollary}

The result is a combination of Proposition \ref{mfisR}, Theorem \ref{celok6} and \ref{thm:globalpoint2f}. We remark that in the typical compressed sensing application, $A$ is a matrix with $m<<n$ and $K<<m$. If the columns of $A$ are normalized random, then the conditions on $A$ are satisfied with probability 1. Moreover, any subset of $2K$ columns will be close to an isometry as long as $2K<<m$, so it is not unreasonable to expect that $\beta_{2K}\approx 1$. In this case the assumption \eqref{n} is quite reasonable since $|\tilde z'_{K+1}|\leq |\tilde z'_{K}|$ by construction and $2\beta_{2K}^2-1\approx 1.$ The size of $\beta_{2K}$ in the above scenario is further discussed in subsection \ref{sec:size}.

We now consider the case when $b=Ax_0+\ep$ and we wish to retrieve $x_0$, where $\card(x_0)=K$. By combining Proposition \ref{p1f} and Theorem \ref{cor:dogadgetf}, we have (for $A$ as in the previous corollary);

\begin{corollary}\label{cor:doctorgadget2}
If $\beta_{2K}>\frac{1}{\sqrt{2}}$ and  $|x_{0,j}|>\para{\frac{1}{2\beta_{2K}^2-1}+\frac{1}{\beta_K}}\|\ep\|$ for all $j\in S$ then there exists a unique local minimizer $x'$ to $\ksir$ with $\supp (x')=\supp (x_0)$. This is the global minimum of both $\K_K$ and $\ksir$ and moreover it satisfies $\|Ax'-b\|\leq \|\epsilon\|$, $\supp (x')=\supp(x_0)$ and $$\|x'-x_0\|\leq \frac{\|\ep\|}{\beta_K}.$$
\end{corollary}

If $\beta_{2K}\approx 1$ the condition is $|x_{0,j}|\gtrsim 2\|\ep\|$ and the conclusion $\|x'-x_0\|\lesssim{\|\ep\|}.$ We further remark that $x'$ in Corollaries \ref{cor:doctorgadget} and \ref{cor:doctorgadget2} is the so called ``oracle solution'', i.e. the one you would get if an oracle told you the true support $S$ \begin{wrapfigure}{r}{0.4\textwidth}
  \begin{center}
     \includegraphics[width=.4\textwidth]{17x25.pdf}\\
  \end{center}
 \caption{Plot of $\frac{1}{\beta_K}$ for a $17\times 25$ matrix $A$ with normalized random columns.}\label{f2}
\end{wrapfigure}
 of $x_0$ and you were to solve the (overdetermined) equations system $A_Sx=b$ where $A_S$ denotes the $m\times K$ matrix whose columns are those with indices in $S$ (and then expand $x$ to $\R^n$ by inserting zeroes off $S$). This is clearly the best
possible solution one could hope for (as argued also in \cite{candes2006stable}). If we have a method that would find a vector $x'$ with the correct support $S$ (with a bias or not), we can always get this unbiased solution by simply discarding $x'$ and follow the above procedure to get the oracle solution. Therefore the issue of finding the support is maybe more central than having a good estimate of $\|x'-x_0\|$. Indeed, finding the correct support is often used as a measurement of success in numerical sections on the topic \cite{blumensath2009iterative,candes2008enhancing,loh2017support}. Apart from \cite{blumensath2009iterative} which studies the minimization of \eqref{q1} itself (and performs poor in practice, see Figure \ref{f4}), we have not been able to locate any results in the literature which claim to find $S$, as Corollaries \ref{cor:doctorgadget} and \ref{cor:doctorgadget2}.

 In \cite{nikolova2013description} and \cite{nikolova2016relationship}, the minimizers of the un-regularized functionals $\K$ and $\K_K$ are studied. Corollaries \ref{cor:globalpoint2}-\ref{cor:doctorgadget2} provide new results and extensions of this line of research.

\subsection{On the size of RIP/RLIP-constants}\label{sec:size}

We are interested in estimating the size of the constants $\beta_K$, $\delta_K$ as well as compare the upper bound $C_K$ in \eqref{crt} with $1/\beta_{K}$ in the corresponding estimates of Corollary \ref{cor:doctorgadget} and \ref{cor:doctorgadget2}. We focus on matrices $A$ of size $m\times n$ where $n>m$ and the columns are generated from a random Gaussian distribution and then normalized so that $\|A\|_{\infty,col}=1$, in accordance with \cite{candes2006stable,donoho2006most} as well as the the assumptions in this paper.

\begin{figure}
     \includegraphics[width=.45\textwidth]{512x25.pdf}
     \includegraphics[width=.45\textwidth]{512x25zoom.pdf}\\
 \caption{Left; $C_K$ (red, $K=1\ldots 5$) versus $\frac{1}{\beta_K}$ (blue, $K=1\ldots 19$) for a $512\times 25$ matrix $A$ with normalized random columns. Right, zoom on $\frac{1}{\beta_K}$.}\label{f3}
\end{figure}

\iffalse
We remind the reader that a ``good'' RIP constant $\delta_j$ is $\approx 0$ whereas a good RLIP-constant $\beta_j$ is $\approx 1$. As we will show below, the $\beta_j$'s seem more keen on being ``good''. One explanation for this is clearly that the $\delta_j$'s are designed to satisfy two inequalities as opposed to one, but moreover, in case the lower inequality defines $\delta_j$, we have $$\delta_j=\sqrt{1-\beta_j^2},$$ and both the square and the square root work against ``good'' values for $\delta_j$. To illustrate, if $\beta_K=0.9$ (which is a decent value) we see that $1-\beta_K^2\approx 0.2$ so $\delta_K\approx 0.45$, which is a bad value of $\delta_K$. Worse yet, in order for \eqref{crt} to be satisfied, we need \eqref{ki} which requires $\delta_{4K}$ ($\delta_{3K}$ is enough for the results in \cite{blumensath2009iterative}) to be small, which is even harder. In contrast, the results of this paper apply whenever $\beta_{2K}$ is decent. For these reasons, it turns out that \eqref{crt} is almost never satisfied for a $17\times 25$-matrix $A$ and $K=2$(!!), which is why these are omitted from Figure \ref{f2} where we plot values of $1/\beta_K$ for $A$ of this size. Although this may seem too small for a realistic application, we remark that matrices of this size do appear e.g.~ in GPS-positioning \cite{lesouple}. Interestingly, the values of $1/\beta_{K}$ are decent until around $K=7$, which roughly coincides with the upper theoretical bound $m/2=8.5$ for when it is reasonable to expect that any method would work \cite{donoho2006most}.
\fi

Figure~\ref{f2} shows numerical computations of $1/\beta_K$ for random matrices of size $17 \times 25$. Here we do not plot $C_K$ since the requirement $\delta_{3K}+3\delta_{4K} < 2$ turned out to almost never be fulfilled when $K > 1$. In contrast, Corollary~\ref{cor:doctorgadget} apply whenever $\beta_{2K}>0$
and Corollary~\ref{cor:doctorgadget2} when $\beta_{2K}>\frac{1}{2}$.

In order to compare $1/\beta_K$ with $C_K$ for a moderately sized application, we would like to compute these for a $256\times 512$-matrix, say. However, due to the combinatorial nature of the constants $\delta_j$ and $\beta_k$, it is not possible to compute them for matrices with more columns than $\approx 30$ (on a standard laptop at least). Nevertheless a $256\times 25$-matrix can be seen as the first portion of a $256\times 512$-matrix, and from this perspective the values obtained in the $256\times 25$-case serve as lower bounds of the true values. It turns out that \eqref{ki} typically does not hold for $K > 2$, while $\beta_{2K} > 1/2$ holds for all $K$ up to 25.

Finally, considering $512\times 25$-matrices, we do have that \eqref{ki} is satisfied in general, and Figure \ref{f3} plots a graph of $1/\beta_K$ versus $C_K$. From the right graph we also see that values of $\beta_K$ are very decent, around 0.8, for $K$ near 20.

\subsection{Numerical Recovery Results}\label{sec:num}

In \cite{candes2008enhancing} astonishing results are shown in the noise free case, for example in Figure 2 (of that paper) we see how $K=130$ non-zero entries are recovered using a matrix $A$ of size $m\times n= 256\times 512$ (which incidentally is close to the theoretical bound $2K<m$ in the present paper). However, in the presence of noise, performance seems to drop drastically. In Figure 7 (of the same paper) we see an example where $K=8$, $m=72$ and $n=256$. This is in line with the predictions of \cite{loh2017support}, which use $K=\sqrt{m}$ in their numerical section 4.3.

\begin{figure}[htb]
     \includegraphics[width=.5\textwidth]{x0mu=1_StepLength09.pdf}
     \includegraphics[width=.5\textwidth]{xSmu=1_StepLength09.pdf}\\
 \caption{$\|x'-x_0\|$ (left) and $\|x'-x_S\|$ (right) versus $\|\epsilon\|$ for the 5 methods \eqref{l1probdual}, \eqref{q1}-\eqref{q1reg} and \eqref{q2}-\eqref{q2reg}. The methods based on $\Q_2(\card)$ and $\Q_2(\iota_{P_K})$ work perfectly down to $SNR\approx 4$.}\label{f4}
\end{figure}

Here we will present numerical results for the case of $K=10$, $m=100$ and $n=200$.
We use a matrix $A$ with Gaussian randomly generated columns, which are subsequently normalized, and solve problems \eqref{l1probdual}, \eqref{q1reg} and \eqref{q2reg} for $b=Ax_0+\epsilon$ for different levels of noise $\|\epsilon\|$ between 0 and 5. The vector $x_0$ has random entries between 2 and 4 in magnitude, and a total magnitude $\|x_0\|=11$. To solve the optimization problems we use FBS which is known to converge to a stationary point (by \cite{attouch2013convergence} in combination with Section 2.4 of \cite{carlsson2016convexification} or Section 6 of \cite{carlsson2018convex}). In Section 5 of \cite{attouch2013convergence} the convergence of FBS for the unregularized problems \eqref{q1} and \eqref{q2} is considered, but with no analysis of performance. This has also been proposed earlier in \cite{blumensath2008iterative} where it is compared against matching pursuit. For this reason, we also included graphs for the result of minimizing \eqref{q1} and \eqref{q2}.

Each point on the respective curves is an average over 50 trials, where we have used 1000 iterations and with a step-size parameter of \(0.9/\|A\|^2\), which is close to the upper theoretical bound given in \cite{attouch2013convergence} (which coincides with the bound for the convex case, see e.g. \cite{combettes2005signal}). For the $\ell^1$-problem \eqref{l1probdual} we used the formula $$\lambda= \frac{\|\epsilon\| }{\sqrt{n}}\sqrt{2 \log (n)}  $$ corresponding to the recommendations in Section 5.2 of \cite{chen2001atomic}. For \eqref{q1}-\eqref{q1reg} we used $\mu=1$ and $K$ was set to 10 for \eqref{q2}-\eqref{q2reg}.

If the values of $\beta_{2K}$ and $\beta_K$ are $\approx 1$, then the conditions in Corollary \ref{cor:doctorgadget} hold given that $2\sqrt{\mu}<\min \{|x_{0,j}|:|x_{0,j}|\neq 0\}$ which in our case is $2.05$ and $\|\epsilon\|\leq \sqrt{\mu}$, whereas the conditions  in Corollary \ref{cor:doctorgadget2} hold as long as $2\|\epsilon\|<2.05$. In both cases, the estimate for $\|x'-x_0\|$ reads $\|x'-x_0\|\lesssim \|\epsilon\|$ which is supposed to hold for $\|\epsilon\|\lesssim 1$. As can be seen from the graph in Figure \ref{f4} (left) the true bound (for this particular example) seems to be $\|x'-x_0\|\lesssim \frac{1}{3}\|\epsilon\|$ for both \eqref{q1reg} and \eqref{q2reg}, whereas the true constant for $\ell^1$ is around 1 (despite $C_{10}=\infty$ as argued earlier).
 The unregularized cardinality problem \eqref{q1},
a.k.a.~iterative hard thresholding, seems to perform poorly (with our parameters) whereas \eqref{q2} (a.k.a. the $K$-sparse algorithm \cite{blumensath2008iterative}) seems to do a decent job, similar to $\ell^1$ in performance for\begin{wrapfigure}{r}{0.5\textwidth}
  \begin{center}
     \includegraphics[width=.5\textwidth]{x0_50x200.pdf}\\
  \end{center}
 \vspace{-0.5cm}\caption{Same as Figure \ref{f5} but with 50 only rows in $A$.}\label{f6}\vspace{-0.5cm}
\end{wrapfigure} higher noise levels. In both cases corresponding
 performance for the regularized versions is significantly better, indicating that the regularization by $S_2^2$ indeed has a crucial effect. Note that all 3 methods work for noise-levels much greater than stipulated by the theory. We also remark that, rather surprisingly, there is no major difference between \eqref{q1reg} and \eqref{q2reg} for moderate noise levels. However, both these methods are designed to find the oracle solution $x_S$, not $x_0$, so to evaluate this performance we include in Figure \ref{f4} (right) also the graph of $\|x'-x_S\|$ versus $\|\epsilon\|$. From this we deduce that both work perfectly until $\|\epsilon\|=3$, but that \eqref{q1reg} deteriorates substantially faster beyond this point. In other words, in this example both methods based on $\Q_2(\card)$ and $\Q_2(\iota_{P_{10}})$ work as expected down to $SNR$ around 4. Note that, in the best case scenario $\beta_K=\beta_{2K}=1$, and then a simple computation shows that Corollary \ref{cor:doctorgadget} and \ref{cor:doctorgadget2} then applies for $SNR$ down to $2\sqrt{10}\approx 6$, and hence there is almost perfect harmony between theory and numerical results. More precisely, we can allow 50\% more noise in practice than predicted by the theory.

In Figure \ref{f6} we show the same graphs except that now $A$ has size $50\times 200$. Clearly this has a significant impact on performance. In particular, although \eqref{q1reg} and \eqref{q2reg} still do better than traditional $\ell^1$-minimization, there is no longer a significant difference. This could indicate that the convex $\ell^1$-method is more reliable in very difficult scenarios, as opposed to the non-convex methods suggested here, but this would have to be further investigated to be confirmed. A drawback of $\ell^1$-methods is that one often needs to find a suitable $\lambda$, which leads to slow evaluation in practice.

\begin{wrapfigure}{r}{0.5\textwidth}
  \begin{center}
     \includegraphics[width=.5\textwidth]{reshapedhisto_100x200.pdf}\\
  \end{center}
\vspace{-0.5cm} \caption{Histogram of cardinality for 50 trials of \eqref{q1reg} with $\|\epsilon\|=2.5$.}\label{f5}
\end{wrapfigure}

Another issue that we have not discussed is the starting point. We have used $0$ for all examples above, and (a bit surprisingly) this seems to work better than using the least squares solution \(x_{LS}\) of $Ax=b$. In our final graph Figure \ref{f5} we plot a histogram of the cardinality of $x'$ over 50 trials with the noise level $\|\epsilon\|=2.5$, using $\Q_2(\card)$ and \(x_{LS}\) as starting point. For this noise level and starting point, $\Q_2(\iota_{10})$ still works perfectly, which is why its performance is excluded, the histogram hits 50 at $K=10$. It is interesting to note the following dichotomy, either the cardinality is around 10, or substantially larger, in harmony with the results presented in this paper (e.g.~Corollary \ref{cor:globalpoint2} and more generally Theorem \ref{thm:statpoint:vec}).

\subsection{Brief review of related results}\label{review}

As previously mentioned, $\Q_2(\card)$ was introduced previously in \cite{zhang2010nearly} and \cite{soubies-etal-siims-2015}, and appeared earlier also e.g.~in \cite{fan2001variable}, although in this paper they move on to introduce yet another penalty called SCAD which we discuss further below. Needless to say, we are not the first group to address the shortcomings of traditional $\ell^1$-minimization by use of non-convex penalties. In fact, even before the birth of compressed sensing, the shortcomings of $\ell^1$-techniques were debated and non-convex alternatives were suggested, we refer to \cite{fan2001variable} for an overview of early publications on this issue. Moreover, shortly after publishing the celebrated result \eqref{crt}, Cand\`{e}s, Wakin and Boyd suggested an improvement called ``Reweighted $\ell^1$-minimization'' \cite{candes2008enhancing} which also became a big success. They provide a theoretical understanding of this algorithm as minimizing the non-convex functional $$f(x)=\sum_j \log(\epsilon+|x_j|)$$ where $\epsilon$ is a parameter chosen by the user. Figure \ref{S22card} shows the functions $\card(x),$ $|x|$ and $\log(0.1+|x|)-\log(0.1)$ as well as $\Q_2(\card)$. As is clear to see, $\log(0.1+|x|)-\log(0.1)$ is closer to $\card(x)$ than $|x|$, which may explain the better performance by reweighted $\ell^1$-minimization reported in \cite{candes2008enhancing}.
The functional $\Q_2(\card)$ is even closer to $\card(x)$, and while this certainly is one reason behind the superior theoretical results reported in this paper, it is not clear that it is beneficial in practice since it may lead to an increased probability of getting stuck in local minima. Indeed, suppose one has a non-sparse solution to $Ax'=b$ where all non-zero elements of $x'$ are in the flat part of $\Q_2(\card)$, then we clearly have an (undesired) local minima of $\kfir(x)=\Q_2(\card)(x)+\|Ax-b\|^2_2$, whose presence for high levels of noise is clearly visible in Figure \ref{f5}. This is further studied in \cite{soubies-etal-siims-2015} where it is shown that, for a particular choice of $7\times 15$-matrix $A$ and other parameters, the original functional \eqref{q1} has roughly 16000 (!) local minima, whereas around 5000 of these remain as stationary points for the regularization \eqref{q1reg}. Several of these stationary points turn out to not be local minima, and hence the authors provide a macro algorithm to avoid non-local minima. In the same vein, Zhang \cite{zhang2010nearly} proposes to iteratively update relevant parameters to reach the desired global minima with higher probability.

While these results speak a bit in favor of using another method such as reweighted $\ell^1$ or $\Q_2(\iota_{P_K})$, which according to Corollary \ref{cor:doctorgadget2} does not suffer from the same drawbacks (under mild assumptions), favorable results for $\Q_2(\card)$ were reported in \cite{loh2017support}, which compares the use of $\Q_2(\card)$/MCP with $\ell^1$ and reweighted $\ell^1$ (called LSP in \cite{loh2017support}) as well as SCAD (which has similar performance as $\Q_2(\card)$). The numerical results in this paper seems also to reconfirm this, despite not employing any algorithm ensuring that we do not converge to an undesired stationary point. At first glance, this seems to contradict the findings of \cite{soubies-etal-siims-2015} reported above. However, in their experiments they do not use $b=Ax_0$ for some sparse $x_0$ and they also do not use a matrix $A$ with good RLIP-properties.

The best theoretical justification to support the use of $\Q_2(\card)$ seems to be Corollary 1 in \cite{loh2017support} which, under a number of assumptions, prove that $\kfir$ does have a unique stationary point with high probability, and provide an estimate of the type \eqref{crt}.
The setting of \cite{loh2017support} is rather different and we have not been able to verify reasonable values of the involved constants $c_l,c_u,c_\infty,R,\mu,\lambda, \eta, c_1,c_2,c_3$ and $\gamma$ in order to compare the strength of our Corollary \ref{cor:doctorgadget} with Corollary 1 in \cite{loh2017support}. We simply note that they point in the same direction and that Corollary \ref{cor:doctorgadget} holds under simpler conditions. The same remark goes for Theorem 3 in \cite{pan2015relaxed} and Theorem 1 in \cite{fan2001variable}, which provide conditions under which a class of non-convex optimization problems give the same estimate as the ``oracle estimator'', with a high probability.

The papers \cite{attouch2013convergence,blumensath2008iterative} considers \eqref{genprob} for the cases $f(x)=\card(x)$ as well as $f(x)=\iota_{P_K}(x)$, and \cite{attouch2013convergence} show in particular that the FBS-algorithm applied to \eqref{genprob} converges to a stationary point, but a further analysis of this point is not present. Incidentally, this article in combination with Section 2.4 of \cite{carlsson2016convexification} (Section 6 of \cite{carlsson2018convex}) shows that FBS also converges for \eqref{genprobS} under very soft assumptions. For the case $f(x)=\card(x)$, \cite{blumensath2009iterative} goes a bit further and actually provide an estimate of the type \eqref{crt} with the good value $C_K=5$ (independent of $K$), however under the assumption $\delta_{3K}<1/8$ which, in the light of the Section \ref{sec:size}, is not easy to satisfy.

Many other non-convex penalties have been proposed over the years \cite{selesnick2017sparse,bredies2015minimization,chartrand2007exact,pan2015relaxed,zou2008one,fan2004nonconcave,wang2014optimal,loh2013regularized,fan2014strong,zhang2012general,zhang2010nearly,loh2017support,candes2008enhancing,breheny2011coordinate,fan2001variable,mazumder2011sparsenet}, and we make no attempt to review them here. The introduction of \cite{loh2017support} contains a recent overview. A common denominator seems to be that the penalty function has the form $p(x)=\sum_j p_j(x_j)$ where $p_j$ are functions on $\R$ (except the recent contribution \cite{selesnick2017sparse}). In this sense, $\Q_2(\iota_K)$ stands out as an interesting deviation.
\iffalse
In fact, $\Q_2(\card)$ and $\Q_2(\iota_K)$ can be seen as extreme points of a more general framework proposed in \cite{larsson-olsson-ijcv-2016}. Although that paper is written in the setting of matrices and without using the $\S_2$-transform explicitly, it is shown that $S_2^2(f)$ is computable for any functional $f$ of the form $$x\mapsto g(\card(x))$$ where $g$ is a convex increasing function on $\mathbb{N}$. Thus $\card(x)$ arise from the concrete choice $g(t)=t$ whereas $\iota_K(x)$ appears as $g(t)=\iota_{\{t:~t\geq K\}}$. The former is reasonable to use when we have maximum uncertainty about the sought cardinality, the latter when we have no uncertainty. Clearly the more common situation is that of limited uncertainty of the sought support, and the framework clearly allow to tailor-make the function $g$ to fit prior knowledge. We will not pursue this generality in this article, but remark that related proximal operators for $\Q_2(f)$ are somewhat tricky to compute, and for this reason there is a free downloadable code available at ....
\fi

\iffalse
\section{Relaxation and the $\S_\gamma$-transform}\label{regS}
Let $f$ be any $[0,\infty]-$valued functional on $\R^n$, $\C^n$ or for that matter any separable Hilbert space $\H$. The $\S_{\gamma}$-transform, where $\gamma>0$ is a parameter, is designed such that $\S^2_{\gamma}(f)(x)+\frac{\gamma}{2}\|x\|^2$ is the l.s.c. convex envelope of $f(x)+\frac{\gamma}{2}\|x\|^2$. It can be shown that $\S^2_\gamma(f)$ is continuous wherever it is finite, and that $\gamma$ is the maximum negative curvature of $\S^2_\gamma(f)$. It also holds that $\S^2_\gamma(f)(x)$ increase with increasing $\gamma$, that $\lim_{\gamma\rightarrow\infty}\S^2_{\gamma}(f)=f$ and that $\lim_{\gamma\rightarrow 0^+}\S^2_{\gamma}(f)$ equals a convex minorant above the l.s.c. convex envelope of $f$, which in the cases considered here is identically 0.

Its potential use as a regularizer for problems of the form \eqref{genprob}, i.e. replacing $f(x)+\frac{1}{2}\|A x-b\|^2$ with
\begin{equation}
\S^2_\gamma(f)(x)+\frac{1}{2}\|A x-b\|^2,
\label{rep}
\end{equation}
was investigated in [...] After much discussion we decided to fix $\gamma=2$ and remove the traditional factor $\frac{1}{2}$ in this paper, since it substantially simplifies formulas. This is not a limitation since one can always obtain a such a problem by rescaling $f,~ A$ and $b$.
To see that this can be done, note that a simple computation shows $\S_\gamma^2(f)=\frac{\gamma}{2}\Q_2(\frac{2}{\gamma}f)$ (see [..]) so that \eqref{rep} is equivalent to $$\Q_2(\frac{2}{\gamma}f)(x)+\fro{\frac{A x}{\sqrt{\gamma}}-\frac{b}{\sqrt{\gamma}}}.$$

We henceforth assume that such a rescaling has been done so that we are interested in minimizing
\begin{equation}\label{relax}\K_{reg}(x)=\Q_2(f)(x)+\fro{{A x-b}}\end{equation} instead of $\K(x)=f(x)+\fro{A x-b}$.

\fi

\section{Uniqueness of minimizers and stationary points with the desired property}\label{sec:unique}
We now turn to the heart of the matter, namely uniqueness of sparse minimizers of $\K_{reg}$, more precisely minimizers in a given $K$-sparse set $P_K$.
As noted in the introduction, this is not possible without imposing additional conditions on $A$ as well as $b$. In this section we provide such a condition and in the coming ones we show what it entails in practice for the sparsity (and $K$-sparsity) problem.

We first introduce the concept of a stationary point for a non-convex functional $g$, which in practice is easier to find than local minimizers. We recall that the Fr\'{e}chet subdifferential $\hat \partial g(x)$ is the set of vectors $v$ with the property that $$\underset{y\neq x}{\liminf_{y\rightarrow x}}~ g(y)-g(x)-\scal{v,y-x}\geq 0.$$
We say that a point $x$ is a stationary point of $g$ if $0\in\hat \partial g(x)$. For the case when $g$ is a sum of a convex function $g_c$ and a differentiable function $g_d$, it is easy to see that $x$ is a stationary point if and only if $-\nabla g_d(x)\in \partial g_c(x)$ where $\partial g_c(x)$ denotes the usual subdifferential. Set \begin{equation}\label{gdef}\G(x)=\frac{1}{2}\Q_2(f)(x)+\frac{1}{2}\fro{x},\end{equation} i.e. $2\G$ the l.s.c. convex envelope of $f(x)+\fro{x}$.
We have
\begin{equation}\label{fr3}\K_{reg}(x)=2\G(x)-\fro{x}+\fro{Ax-b}\end{equation}
which upon differentiation yields that $x'$ is a stationary point of $\K_{reg}$ if and only if
\begin{equation}\label{sp}(I-A^* A)x' + A^* b\in\partial \G(x').\end{equation}
Given any $x$, we therefore associate with it a new point $z$ via
\begin{equation}\label{y}
z=(I-A^* A)x + A^* b.
\end{equation}
The importance of $z$ is due to the following simple observation.

\begin{proposition}\label{thm:statpoint}
Let $x'$ and $x''$ be distinct stationary points of $\K_{reg}$ such that $x''-x'\in P_K$. Then
\begin{equation}\label{ineq}\re\scal{z''-z',x''-x'}\leq (1-\beta_K^2)\fro{x''-x'}.\end{equation}
\end{proposition}

The above proposition will mainly be used backwards, i.e.~we will show that \eqref{ineq} does not hold and thereby conclude that $x''-x'\not\in P_K$.

\begin{proof}
We have $$z''-z'=( I-A^* A)x''+A^*b-( I-A^* A)x'-A^*b=(I-A^* A)(x''-x'),$$
so taking the scalar product with $x''-x'$ gives $$\re\scal{z''-z',x''-x'}=\fro{x''-x'}-\fro{A(x''-x')}\leq (1-\beta_K^2)\fro{x''-x'},$$ as desired. Note that it is not necessary to take the real part, but we leave it since scalar products in general can be complex numbers.
\end{proof}

As we shall see, the point $z'$ has a decisive influence on the coming sections. To begin with, it has the following interesting property.

\begin{proposition}
A point $x'$ is a stationary point of $\K_{reg}$ if and only if it solves the convex problem $$x'\in\argmin_x \Q_2(f)(x)+\fro{x-z'}.$$
\end{proposition}
Note the absence of $A$ in the above formula, which in particular implies that $\Q_2(f)(x)+\fro{x-z'}$ is the convex envelope of $f(x)+\fro{x-z'}$.
\begin{proof}
As noted in \eqref{sp}, $x'$ is a stationary point of $\K_{reg}$ if and only if $z'\in\partial\G(x')$. By the same token, $x'$ is a stationary point of $$\Q_2(f)(x)+\fro{x-z'}=2\G(x)-2\scal{x,z'}+\fro{z'}$$ if and only if $z'\in\partial\G(x')$, and since the functional is convex (and clearly has a well defined minimum) the stationary points coincide with the set of minimizers.
\end{proof}

\section{The sparsity problem}\label{seccard}

We return to the sparsity problem, and consider $f(x)=\mu\card(x)$ where $\mu$ is a parameter and $\card (x)$ is the number of non-zero entries in the vector $x$. In this case we have,
\begin{equation}\label{l0000}\Q_2(\mu\card)(x)=\sum_{j=1}^n \mu-\para{\max\{\sqrt{\mu}-{ |x_j|},0\}}^2, \quad x\in\R^n.\end{equation}
To recapitulate, we want to minimize \eqref{q1}, i.e.~\begin{equation}\label{t57}\kfi(x)=\mu\card(x)+\fro{Ax-b}\end{equation} which we replace by \eqref{q1reg}, i.e. \begin{equation}\label{fr2}\kfir(x)=\Q_2(\mu\card)(x)+\fro{Ax-b}.\end{equation}

\subsection{Equality of minimizers for $\kfi$ and $\kfir$}

As noted by Aubert, Blanc-Feraud and Soubies (see Theorems 4.5 and 4.8 in \cite{soubies-etal-siims-2015}),
$\kfir$ has the same global minima and potentially fewer local minima than $\kfi$ if \begin{equation}\label{alpha}\|A\|_{\infty,col}=\sup_i \|a_i\|_2\leq 1,\end{equation} where $a_i$ denotes the columns of $A$. Below we (essentially) reproduce their statement in the terminology of this paper, and also include a proof for completeness.

\begin{theorem}\label{celok5}
If $\|A\|_{\infty,col}<1$, then any local minimizer of $\kfir$ is a local minimizer of $\kfi,$ and the (nonempty) set of global minimizers coincide. If merely $\|A\|_{\infty,col}=1$, then any connected component of global minima of $\kfir$ includes at least two global minima of $\kfi$.
\end{theorem}

\begin{proof}
We first establish that $\inf \kfi=\inf \kfir$. Since $\kfi\geq \kfir$ it suffices to show that $\inf \kfi\leq \inf \kfir$. Suppose not and let $x_0$ be a point such that $\kfir(x_0)<\inf \kfi$. Then there must be some index $j$ such that the corresponding value in $\Q_2(\mu\card)(x_0)$ is different from $\mu\card (x_{0,j})$, which (see \eqref{l0000}) implies that \begin{equation}\label{py1}0<|x_{0,j}|<\sqrt\mu.\end{equation} But then \begin{equation}\label{py}\partial_{x_{0,j}}^2\kfir(x_0)=-2+2\|a_j\|^2\leq 0.\end{equation} It follows that we can redefine $x_{0,j}$ to equal either $0$ or $\sqrt{\mu}$, so that the resulting point $x_1$ satisfies $\kfir(x_1)\leq \kfi(x_0)$. We can now continue like this for another index $j$ such that \eqref{py1} holds (if it exists), and this process must terminate after finitely many steps $N$. Denoting the resulting point by $x_N$, we see that it satisfies $\kfi(x_N)=\kfir(x_N)<\inf \kfi$, a contradiction.

It is easy to see that $\kfi$ has global minimizers, and by the above argument these are also global minimizers for $\kfir$. Now let $x_0$ be a global minimizer of $\kfir$ but not for $\kfi$. As before we have that \eqref{py1} and \eqref{py} holds for some index $j$, and we clearly must have equality in the latter. If $\|A\|_{\infty,col}<1$ this is a contradiction, and hance we see that the global minimizers of $\kfi$ and $\kfir$ coincides. If merely $\|A\|_{\infty,col}=1$, then we can redefine $x_{0,j}$ to equal either $0$ or $\sqrt{\mu}$ without changing the value of $\kfir$, and as before this process eventually leads to a point $x_N$ which is also a global minimizer for $\kfi.$ By the construction, there are at least two such points.

It remains to prove the statement about local minimizers. If $x_0$ is a local minimizer of $\kfir$ and $\|A\|_{\infty,col}<1$, we immediately get a contradiction from \eqref{py} unless $\kfi(x_0)=\kfir(x_0)$. In view of $\kfi\geq \kfir$, this establishes the claim.
\end{proof}

\subsection{On the uniqueness of sparse stationary points}\label{erai}

Next we take a closer look at the structure of the stationary points. Given $N$ such that $\beta_{N}> 0$, we will show that under certain assumptions the difference between two stationary points always has at least $N$ elements.
Hence if we find a stationary point with less than $N/2$ elements then we can be sure that this is the sparsest one. The main theorem reads as follows:

\begin{theorem}\label{thm:statpoint:vec}
Let $x'$ be a stationary point of $\kfir$, let $z'$ be given by \eqref{y}, and assume that
\begin{equation}\label{e4}|z_i'|\not\in\left[{\beta_{N}^2}{\sqrt{\mu}},\frac{1}{\beta_{N}^2}{\sqrt{\mu}}\right]\end{equation} for all $i\in\{1,\ldots,n\}$ (where the condition is automatically fulfilled if $\beta_N>1$.)
If $x''$ is another stationary point of $\kfir$ then $\card(x''-x') > N$.
\end{theorem}

Note that we allow $\beta_N>1$ in the above theorem, in which case the condition on $z'$ is automatically satisfied. The proof depends on a sequence of lemmas, and is given at the end of the section. Clearly, we will rely on Proposition \ref{thm:statpoint}, which requires an investigation of the functional $\G$ \eqref{gdef} and in particular its sub-differential. Introducing the function $g$ as
\begin{equation}
g(x) =
\begin{cases}
\frac{\mu + {x^2}}{2} & |x| \geq {\sqrt{\mu}} \\
\sqrt{\mu}|x| & 0 \leq |x| \leq {\sqrt{\mu}}
\end{cases}.
\label{eq:gdef}
\end{equation}
we get \begin{equation}\label{Gg}
\G(x)=\sum_{j=1}^n g(x_j).\end{equation}
Its sub-differential is given by
\begin{equation}
\partial g(x) =
\begin{cases}
\{ x\} & |x| \geq {\sqrt{\mu}} \\
\{\sqrt{\mu}\frac{x}{|x|}\} & 0 < |x| \leq {\sqrt{\mu}} \\
\sqrt{\mu}~\D & x = 0
\end{cases}
\label{eq:vectorsubgrad}
\end{equation} where $\D$ is the closed unit disc in $\C$ or, if working over $\R$, $\D=[-1,1]$. In the remainder we suppose for concreteness that we work over $\C$ (but show the real case in pictures).
Note that the sub-differential consists of a single point for each $x \neq 0$.
Figure~\ref{fig:gfunk} illustrates $g$ and its sub-differential.
\begin{figure}[htb]
\begin{center}
\includegraphics[width=40mm]{gfunk}
\includegraphics[width=40mm]{gsubgrad}
\end{center}
\caption{The function $g(x)$ (left) and its sub-differential $\partial g(x)$ (right). Note that the sub-differential contains a unique element everywhere except at $x=0$.}
\label{fig:gfunk}
\end{figure}

The following two results establish a bound on the sub-gradients of $\G$.  We begin with some one-dimensional estimates of $g$.

\begin{lemma}\label{lemma:bnd1}
Assume that $z_0 \in \partial g(x_0)$ and $\beta_N<1$.
If
\begin{equation}
\left|
z_0
\right| > \frac{\sqrt{\mu}}{\beta_N^2}
\label{eq:subgradbnd1}
\end{equation}
then for any $x_1,~z_1$ with $z_1\in \partial g(x_1)$ and $x_1\neq x_0$, we have
\begin{equation}\label{fd}
\re(z_1 -z_0)\overline{(x_1-x_0)} > (1-\beta_N^2) |x_1-x_0|^2 .
\end{equation}
\end{lemma}
\begin{proof}
By rotational symmetry (i.e. $\partial g(e^{i\phi}x)= e^{i\phi} \partial g(x)$), it is no restriction to assume that $z_0>0$. By $\frac{1}{\beta_N^2}> 1$ and \eqref{eq:subgradbnd1}, we see that $z_0>\sqrt{\mu}$, and hence the identity $z_0\in\partial g(x_0)$ and \eqref{eq:vectorsubgrad} together imply that $z_0=x_0$ and in particular that $x_0\in\R$ and
\begin{equation}
\label{onion}x_0>\frac{\sqrt{\mu}}{\beta_N^2}.
\end{equation}
To prove the result we now minimize the quotient
$\frac{\re(z_1 -z_0)\overline{(x_1-x_0)}}{ |x_1-x_0|^2}$ and show that it is larger than $1-\beta_N^2$.
There are three cases to consider; $|x_1|=0$, $0<|x_1|<\sqrt{\mu}$ and $|x_1|\geq \sqrt{\mu}$. The latter case is easy since then $z_1-z_0=x_1-x_0$ and $1-\beta_N^2 < 1$, which yields the desired conclusion.

For the two other cases we first show that $z_1$ and $x_0$ can be assumed to be real.
If $x_1=0$ then the optimization of the above quotient is equivalent to minimization of $-\re(z_1)$ over $z_1 \in \sqrt{\mu}\D$, since $x_0=z_0$ is real and positive, which is clearly minimized in $z_1 = \sqrt{\mu}$.
For the middle case, $z_1$ and $x_1$ have the same angle with $\R$, and $|x_1|<|z_1|<z_0$. We first hold the radii fixed and only consider the angle as an argument. Recall $z_0=x_0$ and set $R=|z_1|/|x_1|$. Then
\begin{equation}\label{gt}\frac{\re(z_1 -z_0)\overline{(x_1-x_0)}}{ |x_1-x_0|^2}=\frac{R|x_1|^2-2R\re x_1 \overline{x_0}+|x_0|^2}{ |x_1|^2-2\re x_1 \overline{x_0}+|x_0|^2}=R-\frac{R-1}{|x_1-x_0|^2}\end{equation}
which shows that the quotient is minimized when $x_1$ is real and $0<x_1<\sqrt{\mu}$ (which then automatically applies to $z_1$ as well).

Summarizing the above we may thus assume that $x_1$ and $z_1$ are real and non-negative and $0\leq x_1<\sqrt{\mu}$. This simplifies the quotient \eqref{gt} to $\frac{x_0-z_1}{ x_0-x_1}$. We now hold $x_1,~z_1$ fixed and consider $x_0$ as the variable. Since $z_1\geq x_1$, it is easy to see that this is minimized for $x_0$ as small as possible, i.e. $x_0=\frac{\sqrt{\mu}}{\beta_N^2}$. With this at hand, the minimum of $\frac{|z_1-\frac{\sqrt{\mu}}{\beta_N^2}|}{ |x_1-\frac{\sqrt{\mu}}{\beta_N^2}|}$ is clearly attained at $x_1=0$ and $z_1=\sqrt{\mu}$. Summing up, we have that
$$\frac{\re(z_1 -z_0)\overline{(x_1-x_0)}}{ |x_1-x_0|^2}>\frac{|z_1-\frac{\sqrt{\mu}}{\beta_N^2}|}{ |x_1-\frac{\sqrt{\mu}}{\beta_N^2}|}\geq \frac{|\sqrt{\mu}-\frac{\sqrt{\mu}}{\beta_N^2}|}{ |\frac{\sqrt{\mu}}{\beta_N^2}|}=1-\beta_N^2.$$
\end{proof}

\begin{lemma}\label{lemma:bnd2}

Assume that $z_0 \in \partial g(x_0)$ and $\beta_N<1$.
If
\begin{equation}
\left|
z_0
\right| < {\beta_N^2}{\sqrt{\mu}}
\label{eq:subgradbnd2}
\end{equation}
then for any $x_1,~z_1$ with $z_1\in \partial g(x_1)$, $x_1\neq x_0$, we have
\begin{equation}\label{fd1}
\re(z_1 -z_0)\overline{(x_1-x_0)} > (1-\beta_N^2) |x_1-x_0|^2.
\end{equation}\end{lemma}
\begin{proof}
The proof is similar to the previous lemma. We first note that $x_0=0$, $x_1\neq 0$ and that $z_0$ may be assumed to be in $(0,\sqrt{\mu}]$. For a fixed radius $R = \frac{|z_1|}{|x_1|}$ the quotient $\frac{\re(z_1 -z_0)\overline{(x_1-x_0)}}{ |x_1-x_0|^2}=\frac{\re(z_1 -z_0)\overline{x_1}}{ |x_1|^2} = R- z_0\frac{\re  x_1}{|x_1|^2}$ is smallest when both $x_1$ and $z_1$ are real valued and positive.
Since $x_1\neq 0$ we have $z_1 = \max(x_1,\sqrt{\mu})$.
It is also easy to see that $z_0={\beta_N^2}{\sqrt{\mu}}$ gives a minimum value for any positive choice of $x_1,z_1$.
This reduces the problem to finding the minimum of $$x_1 \mapsto\frac{\max(x_1,\sqrt{\mu}) -{\beta_N^2}{\sqrt{\mu}}}{ x_1}$$ which by basic calculus equals $(1-\beta_N^2),$ as desired.
\end{proof}

We are now ready to prove Theorem \ref{thm:statpoint:vec}.

\begin{proof}[Proof of Theorem \ref{thm:statpoint:vec}]
By Proposition \ref{thm:statpoint} it suffices to verify \begin{equation}\label{g}
\re\skal{z''-z',x''-x'} > (1-\beta_N^2) \|x''-x'\|^2,\quad x''\neq x'.
\end{equation}
Suppose first that $\beta_N<1$. Since $\partial \G(x)=\sum_{j=1}^n \partial g(x_j)$, Lemmas \ref{lemma:bnd1} and \ref{lemma:bnd2} imply that
$$\re(z''_i-z'_i) \overline{(x_i''-x_i')} > (1-\beta_N^2) |x_i''-x_i'|^2,
$$
for all $i$ with $x_i''-x_i' \neq 0$. Since $x_i''-x_i'=0$ gives $(z''_i-z'_i)\overline{(x_i''-x'_i)}=0$
summing over $i$ gives the result.

Suppose now that $\beta_N>1$. By \eqref{g} it suffices to prove that $\re\skal{z''-z',x''-x'}\geq 0$ for all $x''\neq x'$. Fix $i$ in $\{1,\ldots,n\}$. By rotational symmetry it is easy to see that we can assume that $x'_i,z'_i\geq 0$. Moreover, for fixed values of $|z_i''|$ and $|x''_i|$ (but variable complex phase) it is easy to see that $\re (z_i''-z')(x_i''-x_i')$ achieves min when these are also real, i.e. we can assume that $x''_i,z''_i\in\R$. Since the graph of $\partial g$ is non-decreasing it follows that $(z_i''-z')(x_i''-x_i') \geq 0$ for all $i$, as desired.

It remains to consider the case when $\beta_N=1$, and as above we reach a contradiction if we prove that $\re\skal{z''-z',x''-x'}> 0$. Again we can assume that $x'_i,z'_i\geq 0$ and that $x''_i,z''_i\in\R$. Then \eqref{e4} implies that $z_i'\neq \sqrt{\mu}$ for all $1\leq i \leq n$, which via $z'_i\in \partial g(x'_i)$ also implies that $x_i'\not\in (0,\sqrt{\mu}]$. If $x''\neq x'$ we must have $x''_i\neq x_i$ for some $i$. Using that $z_i''\in \partial g$, examination of \eqref{eq:vectorsubgrad} yields that also $z_i''\neq z_i'$.
With this at hand we see that the left hand side of \eqref{g} is strictly positive, whereas the right equals 0, which again is a contradiction.

\end{proof}

\iffalse
For later use in [..], we record that we have shown the following result. \begin{corollary}\label{corbor}
Let $z'$ satisfy $z'\in\partial \G(x')$ and
\begin{equation}\label{e4t}|z_i'|\not\in\left[{\lambda^2}{\sqrt{\mu}},\frac{1}{\lambda^2}{\sqrt{\mu}}\right].\end{equation}
If $z''\in\partial \G(x'')$, then $\re\scal{z''-z',x''-x'}>(1-\lambda^2)\|x''-x'\|^2$.
\end{corollary}
\fi

\subsection{Conditions on global minimality}\label{erai1}

\begin{theorem}\label{thm:globalpoint2}
Let $A$ satisfy $\|A\|_{\infty,col}\leq 1$, let $x'$ be a stationary point of $\kfir$ and let $z'$ be given by \eqref{y}. Assume that
\begin{equation}\label{cond3}|z_i'|\not\in\left[{\beta_N^2}{\sqrt{\mu}},\frac{1}{\beta_N^2}{\sqrt{\mu}}\right],\quad 1\leq i\leq n.\end{equation}
If \begin{equation}\label{cond2}2\mu\card(x') +\fro{Ax'-b}< \mu N+\mu,\end{equation} then $x'$ is the unique global minimum of $\kfi$ and $\kfir$.
\end{theorem}

Obviously, it is desirable to pick $N$ as large as possible, which is limited by \eqref{cond3} and the fact that $\beta_N$ decreases with $N$. Also note that $\beta_N\leq 1$ since $\beta_1\leq \sup_i\{\|a_i\|_2\}=\|A\|_{\infty,col}$.

\begin{proof}
Set $K=\card(x')$ and assume that $x'$ is not the unique global minimizer of $\kfir$.
By Theorem \ref{celok5}, there exists a global minima $x''\neq x'$ for both $\kfir$ and $\kfi$, which hence is a stationary point of $\kfir$. Theorem \ref{thm:statpoint:vec} then shows that $\card (x'')\geq N-K+1$. It follows that
$$\kfir(x'')-\kfir(x')\geq \kfi(x'')-\kfi(x')\geq \mu(N-K+1)-(\mu K +\fro{Ax'-b})>0$$
by \eqref{cond2}, $\kfi(x'')=\kfir(x'')$ and $\kfi(x')\geq\kfir(x')$. This is a contradiction, and hence $x'$ must be the unique global minimizer of $\kfir$. By Theorem \ref{celok5} it then follows that $x'$ is also unique minimizer of $\kfi$.
\end{proof}

\subsection{Noisy data.}
In this final subsection we return to the compressed sensing problem of retrieving a sparse vector $x_0$ given corrupted measurements $b=Ax_0+\ep$, where $\ep$ is noise and $x_0$ is sparse. More precisely we set $S=\supp x_0$ where we assume that $\#S=K$ is much smaller than $m$ -- the amount of rows in $A$ (i.e. number of measurements). We let $x_{0,j}$ denote the elements of the vector $x_0$. Let $A_S$ denote the matrix obtained from $A$ by setting columns outside of $S$ to $0$, and let $x_S$ denote the least squares solution to $A_S x_S=b$. Note that this is the so called ``oracle solution'' discussed in the introduction, which can also be written $x_S=(A_S^*A_S)^\dagger A_S^*b$ where $(A_S^*A_S)^\dagger$ denotes the Moore-Penrose inverse. The below proposition shows that the oracle solution is under mild assumptions a local minimizer of $\K_{reg}$, which we denote by $x'$ for notational consistency.

\begin{proposition}\label{p1}
Let $A$ satisfy $\|A\|_{\infty,col}\leq 1$. If $\|\ep\|< {\sqrt{\mu}}$ and $$|x_{0,j}|>\sqrt{\mu}+\frac{\|\ep\|}{\beta_K}$$ for all $j\in S$ then the oracle solution $x'=x_S$ is a strict local minimum to $\kfir$ with $\supp (x')=\supp (x_0)$. We also have $|x_{j}'|>\sqrt{\mu},~ j\in S,$ $\|Ax'-b\|\leq \|\epsilon\|$, and $$\|x'-x_0\|\leq \frac{\|\ep\|}{\beta_K}.$$
\end{proposition}

\begin{proof}
Consider the equation $A_Sx=Ax_0+\ep$ and note that $Ax_0=A_Sx_0$. The least squares solution is obtained by applying $(A_S^*A_S)^\dagger A_S^*$ which gives the solution $$x'=x_0+(A_S^*A_S)^\dagger A_S^*\ep=x_0+\de,$$ where we set $(A_S^*A_S)^\dagger A_S^*\ep=\de$. By construction of the Moore-Penrose inverse, $\supp \de\subset S$, and hence $$A\de=A_S\de=P_{\text{Ran} A_S}\ep,$$ where $P_{\text{Ran} A_S}$ denotes the orthogonal projection onto the range of $A_S.$ In particular, $$\|\de\|\leq\frac{\|A_S\de\|}{\beta_K}=\frac{\|P_{\text{Ran} A_S}\ep\|}{\beta_K}\leq \frac{\|\ep\|}{\beta_K},$$
which establishes the final inequality in the proposition. Also $\|\de\|_{\infty}\leq \|\de\|_{2}$ which implies \begin{equation}\label{sofg}|x_{j}'|\geq |x_{0,j}|-|\de_j|>\sqrt{\mu}+\frac{\|\ep\|}{\beta_K}-\frac{\|\ep\|}{\beta_K}=\sqrt{\mu},\quad j\in S.\end{equation} This also gives $\supp x'=\supp x_0$ since we already have shown $\supp x'\subset \supp x_0\cup\supp \de\subset S$.

We now consider $Ax'-b$, which equals \begin{equation}\label{sof}\begin{aligned}&Ax'-b=A_Sx'-b=\\&A_Sx_0+A_S(A_S^*A_S)^\dagger A_S^*\ep-(A_Sx_0+\ep)=(P_{\text{Ran} A_S}-I)\ep=-P_{(\text{Ran} A_{S})^{\perp}}\ep\end{aligned}\end{equation}
and hence $\|Ax'-b\|\leq \|\epsilon\|$.

It remains to prove that $x'$ is a local minimum of $\kfir=\Q_2(\mu\card)+\fro{Ax-b}$. To this end, consider $\kfir(x'+v)$. Since $|x_{j}'|>\sqrt{\mu}$ for $j\in S$, the term $\Q_2(\mu\card)$ is flat for the corresponding indices of $v$. We get \begin{equation}\label{rd}\kfi(x'+v)=\sum_{j\in S^c}\left(2\sqrt{\mu} |v_j|-v_j^2\right)+2\scal{v,A^*(Ax'-b)}+\|Av\|^2+\kfir(x').\end{equation} Since $x'$ solves the least squares problem posed initially, the vector $A_S^*(Ax'-b)=A_S^*(A_Sx'-b)$ must be 0. With this in mind \eqref{rd} then simplifies to \begin{equation}\label{rd1}2\left(\sum_{j\in S^c}\sqrt{\mu} |v_j|+v_j\scal{a_j,Ax'-b}\right)-\sum_{j\in S^c}v_j^2+\|Av\|^2+\kfir(x').\end{equation} By the Cauchy-Schwartz inequality and \eqref{sof} we have $$|\scal{a_j,Ax'-b}|\leq \|a_j\|\|\ep\|< \|A\|_{\infty,col} {\sqrt{\mu}}\leq\sqrt{\mu}.$$ It follows that the term $\sum_{j\in S^c}\sqrt{\mu} |v_j|+v_j\scal{a_j,Ax'-b}$ in \eqref{rd1} can be estimated from below by $\rho\sqrt{\sum_{j\in S^c}v_j^2}$ for some $\rho>0$, and hence that $$2\left(\sum_{j\in S^c}\sqrt{\mu} |v_j|+v_j\scal{a_j,Ax'-b}\right)-\sum_{j\in S^c}v_j^2>0$$ for $v$ in a neighborhood of 0, as long as $\sum_{j\in S^c}v_j^2\neq 0$. To have $\kfir(x'+v)\leq\kfir(x')$ we thus need $\supp v\subset S$, as seen from \eqref{rd1}. But then \eqref{rd1} reduces to $\|Av\|^2+\kfir(x')$, and since $\beta_K>0$ it follows that $\|Av\|^2>0$ unless $v=0$. In other words, $x'$ is a strict local minimizer.
\end{proof}

In the above proposition, there is nothing said as to whether $x'$ is a global minimum or not. To get further, let $z'$ correspond to $x'$ via \eqref{y}. We need conditions such that \eqref{cond3} holds for $z'$, i.e.
\begin{equation}\label{cond31}|z_{i}'|\not\in\left[{\beta_N^2}{\sqrt{\mu}},\frac{1}{\beta_N^2}{\sqrt{\mu}}\right].\end{equation}
We remind the reader that $N$ is a number which preferably is a bit larger than $2K$, where $K$ is the cardinality of $x_0$.

\begin{proposition}\label{p2}
Let $A$ satisfy $\|A\|_{\infty,col}\leq 1$. If $\|\ep\|< {\beta_N^2\sqrt{\mu}}$ and \begin{equation}\label{po7}|x_{0,j}|>\frac{\sqrt{\mu}}{\beta_N^2}+\frac{\beta_N^2\sqrt{\mu}}{\beta_K}, \quad j\in \supp x_0,\end{equation}
then \eqref{cond31} holds.
\end{proposition}
\begin{proof}
Using \eqref{sof} we get
\begin{align}\label{tg}z'=( I-A^* A)x' + A^* b =  x'-A^*(Ax'-b)= x'+A^*P_{(\text{Ran} A_{S})^{\perp}}\ep.\end{align}
Since $A^*P_{(\text{Ran} A_{S})^{\perp}}$ is 0 on rows with index $j\in S$ (being a scalar product of a vector in $\text{Ran} A_{S}$ and another in its orthogonal complement), we see that $z_{j}'= x_{j}'$ for such $j$. Combining this with the final estimate of Proposition \ref{p1}, we see that  \begin{equation*}\label{po9}|z_{j}'|>\frac{1}{\beta_N^2}{\sqrt{\mu}}, \quad j\in S\end{equation*} holds whenever \begin{equation}\label{po6}|x_{0,j}|>\frac{\sqrt{\mu}}{\beta_N^2}+\frac{\|\ep\|}{\beta_K}, \quad j\in S,\end{equation} which is true by the assumptions. For the remaining $z_{j}'$, (i.e. $j\in S^c$), we have $x_{j}'=0$ so \begin{equation}\label{o0}|z_j'|=|(A^*P_{(\text{Ran} A_{S})^{\perp}}\ep)_j|=|\scal{P_{(\text{Ran} A_{S})^{\perp}}\ep,a_j}|\leq \|A\|_{\infty,col}\|\ep\|\leq \|\ep\|<{\beta_N^2}{\sqrt{\mu}},\end{equation}
which establishes \eqref{cond31}.
\end{proof}

Putting all the results together and combining with simple estimates, we finally get.

\begin{theorem}\label{thm:doctorgadget}
Suppose that $b=Ax_0+\ep$ where $A$ is an $m\times n$-matrix with $\|A\|_{\infty,col}\leq 1$ and set $\card (x_0)=K.$ Let $N\geq 2K$ and assume that
$\|\ep\|< {\beta_{N}^2\sqrt{\mu}}$ and $$|x_{0,j}|>\para{\frac{1}{\beta_{N}^2}+1}\sqrt{\mu},\quad j\in \supp x_0.$$ Then the oracle solution $x'=x_S$ is a unique global minimum to $\kfir$ as well as $\kfi$, with the property that $\supp x'=\supp x_0$, that $$\|x'-x_0\|\leq \frac{\|\ep\|}{\beta_K},$$ and that $\card(x'')> N-K$ for any other stationary point $x''$ of $\kfir$.
\end{theorem}

\iffalse
A necessary condition for the above assumptions to hold, is that they hold with $\beta_{N}$ replaced by $\sigma_{N}$, in light of Proposition \ref{p0}.
\fi
\begin{proof}
All the statements follow by Theorem \ref{thm:statpoint:vec}, Theorem \ref{thm:globalpoint2} and Proposition \ref{p1}, so we just need to check that these apply. Note that $\beta_{N}\leq \beta_K\leq \|A\|_{\infty,col}\leq 1$ which will be used repeatedly.

We begin to verify that Proposition \ref{p1} applies, which is easy by noting that $\|\ep\|\leq \beta_N^2\sqrt{\mu}<2\sqrt{\mu}$ and $${\sqrt{\mu}}+\frac{\|\epsilon\|}{\beta_K}\leq \frac{\sqrt{\mu}}{\beta_{N}^2}+\frac{\beta_{N}^2\sqrt{\mu}}{\beta_K}\leq \frac{\sqrt{\mu}}{\beta_{N}^2}+{\sqrt{\mu}}<|x_{0,j}|.$$

Now, to verify that the two theorems apply we need to check the conditions \eqref{cond31}, which follow if we show that Proposition \ref{p2} applies. The estimate on $\|\ep\|$ is satisfied by assumption and the other follows by noting that $\frac{\beta_{N}^2}{\beta_K}\leq 1.$ By this we already have verified Theorem \ref{thm:statpoint:vec} and the first condition of Theorem \ref{thm:globalpoint2}. To check  \eqref{cond2} note that $\|Ax'-b\|\leq \|\ep\|< \beta_N^2\sqrt{\mu}$ by Proposition \ref{p1}, so \eqref{cond2} holds if $2\mu K+\beta_N^4{\mu}\leq \mu N+\mu$, which is clearly the case since $N\geq 2K$.

\end{proof}

As usual, a simpler statement is found by setting $N=2K$, which gives the loosest conditions to verify, (see Corollary \ref{cor:doctorgadget}). The only difference in the conclusion concerns the cardinality of other local minima, since the estimate on $\|x'-x_0\|$ only depends on $\beta_K$.

\section{Known model order; the $K$-sparsity problem}\label{seccardfix}

Let $P_K=\{x:\card (x)\leq K\}$ where $x$ is a vector in $\C^n$ or $\R^n$. Set $f(x)=\iota_{P_K}(x)$ and note that the problem \begin{equation}\label{agt1}\argmin_{\card(x)\leq K}\|Ax-b\|\end{equation} is equivalent to finding the minimum of \begin{equation}\label{agt2}\ksi(x)=\iota_{P_K}(x)+\|Ax-b\|^2,\end{equation}
(where we put a subindex $K$ to distinguish from $\K$ in the previous section). Again, we will approach this problem by using
$$\ksir(x)=\Q_2(\iota_{P_K})(x)+\|Ax-b\|^2.$$
This is in some ways much simpler than the situation in the previous sections, for example all local minimizers of $\ksi$ are clearly in $P_K$.
On the other hand, $\Q_2(\iota_{P_K})$ turns out to be rather complicated. We recapitulate the essentials, which follows by adapting the computations in \cite{andersson-etal-ol-2017} (for matrices) to the vector setting. Define $\tilde x$ to be the vector $x$ resorted so that $(|\tilde x_j|)_{j=1}^d$ is a decreasing sequence. Then

\begin{equation}\label{lust1}\Q_2(\iota_{P_K})(x)= \frac{1}{k_*}\para{\sum_{j>K-k_*}|\tilde{x}_j|}^2-\sum_{j>K-k_*}|\tilde x_j|^2\end{equation} where $k_*$ is the largest value in $1...K$ for which the non-increasing sequence
\begin{equation}\label{lust}s(k)=\left(\sum_{j>K-k}|\tilde x_j|\right)-k|\tilde x_{K+1-k}|\end{equation}
is non-negative (note that it clearly is non-negative for $k=1$). Although it is not very clear from the above expression, $\Q_2(\iota_{P_K})$ is known to be continuous (see e.g.~Proposition 3.2 in \cite{carlsson2018convex}), and this will be used without comment below. We first show that the global minima of $\ksir$ and $\ksi$ coincide.

\subsection{Equality of minimizers and $K$-feasibility}

In order to provide a theorem similar to \ref{celok5}, we need a technical condition on the columns $a_1,\ldots,a_n$ of $A$. We say that $A$ is \textit{$K$-feasible} if $\|A\|_{\infty,col}\leq 1$ and for any subset of $n-K$ columns, we can pick two such that $\|a_i-a_j\|^2\leq 2$. We say that $A$ is \textit{strictly $K$-feasible} if the inequality is strict. This is very easy to satisfy, the following proposition lists conditions that imply $K$-feasibility in $\R$ and $\C$ respectively.
\begin{proposition}\label{mfisR}
If we work over $\R$, any $A$ with $\|A\|_{\infty,col}\leq 1$ and $n\geq m+K+2$ is $K-$feasible. If we add the condition that $\scal{a_i,a_j}\neq 0$ for all pairs, or that $\|A\|_{\infty,col}< 1$, then strict $K-$feasibility follows. The same follows over $\C$ if $n\geq 2m+K+2$. Another condition ensuring strict $K-$feasibility, which works in both $\R$ and $\C$, is that $\|A\|_{\infty,col}\leq 1$ and at least $nK$ of the values $\{\re\scal{a_i,a_j}\}_{i> j}$ are positive (repetitions allowed).
\end{proposition}
We remark that it is possible to choose $2m+1$ vectors in $\C^m$ such that $\|a_i-a_j\|^2> 2$, just consider a simplex in $\R^{2m}$ with equal sidelengths and all corners on the unit sphere. The condition that $n\geq 2m+K+2$ is a bit unfortunate, since it rules out the common situation $n=2m$. This is why we added the final part of the proposition.

\begin{proof}
If the chosen subset contain a zero vector, the conclusion is immediate, so we can assume that this is not the case. For any $m+2$ vectors $a_1,\ldots,a_{m+2}$ in $\R^m$, we can always pick two such that $\scal{a_i,a_j}\geq 0$, which follows from a simple induction argument \cite{mathstack}. The first two conclusions regarding $\R^m$ follow immediately by this observation. Since $\C^m$ is isomorphic with $\R^{2m}$, the corresponding result for $\C$ follows. Finally, the elements above the diagonal in $(\scal{a_i,a_j})_{i,j=1}^n$ are $n(n-1)/2$ in number. When we consider a subset of columns of cardinality $n-K$, we remove a total of $(n-K)K+(K-1)K/2$ of these. Since $nK$ is a bigger number, we are certain that at least one positive value remain.
\end{proof}

To illustrate a concrete example, which sometimes appears in applications, we consider the concatenation of a discrete Fourier transform matrix and an identity matrix. To see what the above proposition entails in this case, suppose that $m=4k$ or $m=4k+1$. Each column of the Fourier matrix gives rise to at least $k$ positive values in its scalar products with the canonical basis coming from the identity matrix, so in total we have at least $mk$ positive off diagonal elements in the Fourier matrix. This gives the condition $2mK\leq mk$, i.e.~$K\leq m/8$, which is acceptable for relevant applications. We now develop the theory for $K$-feasible matrices, starting with the analog of Theorem \ref{celok5}.

\begin{theorem}\label{celok6}
Let $A$ be $K$-feasible. Then the global minimizers of $\ksir$ and $\ksi$ coincides, and all lie in $P_K$. If $A$ is strictly $K$ feasible, then any local minimizer of $\ksir$ lies in $P_K$ and is a minimizer of $\ksi$.
\end{theorem}

\begin{proof} We first treat global minimizers. Clearly all minimizers of $\ksi$ are in $P_K$. Since $\ksi\geq\ksir$ and they coincide on $P_K$, it suffices to show that a given global minimizer of $\ksir$ is in $P_K$. This is annoyingly difficult, it is even a problem to show that $\ksir$ has global minima. We begin by showing that large values of $x$ are not candidates for global minima if they are in the set $$U=\left\{x\neq 0:~\frac{\sum_{j=K+1}^n|\tilde x_j|}{\sum_{j=1}^K|\tilde x_j|}\geq\frac{1}{2K}\right\}.$$ We have $\Q_2(\iota_{P_K})(x)>0$ for all $x\in U$. One way to see this is by Corollary 4.4 in \cite{carlsson2018convex} (or Theorem 2.20 in \cite{carlsson2016convexification}), which states that there exists a direction $v$ such that $t\mapsto \Q_2(\iota_{P_K})(x+tv)>0$ has negative second derivative (since $\ksir(x)<\infty=\ksi(x)$), and this would imply that $\Q_2(\iota_{P_K})$ could take negative values, contradicting Proposition 3.2 in \cite{carlsson2018convex} (or Proposition 2.1 in \cite{carlsson2016convexification}). This can also be deduced by a more careful analysis of \eqref{lust1}, which we will perform below. Put \begin{equation}\label{olbia}\epsilon=\inf\left\{\Q_2(\iota_{P_K})(x): ~x\in U,~\|x\|_2=1\right\}.\end{equation}
Since we are minimizing a continuous non-zero function over a compact set, $\epsilon>0$. We now show that large values of $x\in U$ yield large values of $\Q_2(\iota_{P_K})(x)$. Let us write $s=s_x$ for \eqref{lust}, when there is a need to make the dependence on $x$ clear. The function $s$ is radially dependent, i.e.~$s_{tx}=t s_x$ for $t\in\R$, and hence $k_*$ is radially independent. Looking at the expression for $\Q_2(\iota_{P_K})$ we see that $$\Q_2(\iota_{P_K})(tx)=t^2\Q_2(\iota_{P_K})(x)\quad t\in \R.$$
Note that $\ksi(0)=\ksir(0)=\frac{1}{2}\|b\|^2$ so the global minimum is less than or equal to this. If $R$ is such that $\epsilon R^2>\frac{1}{2}\|b\|^2$, it finally follows that no point $x\in U$ with $\|x\|>R$ can be less than $\frac{1}{2}\|b\|^2$.

We remark in passing that $x=0$ can not be a global minimizer of $\ksir$ unless $b$ is perpendicular to the range of $A$, in which case the theorem holds trivially. To see this, note that
$\Q_2(\iota_{P_K})(0)=0$ and $\Q_2(\iota_{P_K})\geq 0$, so if $x=0$ is the global minimum of $\ksir$ the gradient of $\frac{1}{2}\|Ax-b\|^2$ must necessarily be zero at $x=0$, i.e.~$A^*(-b)=0$.

Now let $G$ be the set of global minimizers for $\ksir$ restricted to $[-R,R]^n$. This set is clearly closed, non-void and bounded. Now let $G_n\subset G$ be the subset where $|\tilde x_n|$ attains its minimum over $G$, let $G_{n-1}\subset G_n$ be the subset where $|\tilde x_{n-1}|$ is minimized, and so on until we reach $G_{K+1}$, which still is closed, non-void and bounded. Suppose that $G_{K+1}\not\subset P_K$ and pick $x\in G_{K+1}\setminus P_K$. We now show that this is impossible. First of all, note that any two columns of $A$ and corresponding two elements in $x$ may (simultaneously) switch positions and sign, without affecting the problem, so it is no restriction to assume that $|\tilde x|=x$, which we now do.

If $x_{K+1}=R$ then this must also be the case for $x_1,\ldots,x_K$, and hence $\|x\|>R$ and $x\in U$, which is impossible by the earlier conclusions. Thus $x_{K+1}<R$.

Use $K$-feasibility of $A$ to pick two indices $j>i> K$ such that $\|a_i-a_j\|^2\leq 2$. Consider the function \begin{equation}\label{function}x(t)=x+t e_i-te_j.\end{equation} We shall show that this function stays in $G$ for small values of $t>0$, which contradicts the construction of $G_{K+1}$. Note that it stays in $[-R,R]^n$ for sure, due to $x_{K+1}<R$.

A complicating factor is the fact that we may fail to have $|\tilde x(t)|=x(t)$ for $t>0$, i.e.~this vector is not necessarily non-increasing as a function of its index. As long as $ x_{K}> x_{i}$, we can pick both $i,j>K$ such that $x(t)$ is non-increasing for small values of $t>0$. We consider this case first. All values of $s_{x(t)}(k)$ in \eqref{lust} are then unaltered by $t$, and hence small perturbations do not affect $k_*$. With this at hand, it follows that the first term in the expression \eqref{lust1} for $\Q_2(\iota_{P_K})(x(t))$ is unaffected by small changes in $t$, whereas the latter term is a quadratic polynomial starting with $-2t^2$. The quadratic term in the expression $\|Ax(t)-b\|^2$ on the other hand is $\|a_i-a_j\|^2t^2$. Using $\|A\|_{\infty,col}\leq 1$, it follows that \begin{equation}\label{po0}\frac{d^2}{dt^2}\ksir(x(t))=-4+2\|a_i-a_j\|^2\leq 0.\end{equation} Thus $\ksir(x(t))$ is linear in a neighborhood of 0, and since $x(0)\in G$ it must actually be a constant. It follows that $x(t)\in G$ for small values of $t>0$, which is a contradiction as we noted before.

It remains to consider the case when $x_{K}= x_{i}$. In this case we can make $x(t)$ non-increasing (of its index) for small (fixed) values of $t>0$, upon changing $i$ so that $x_i$ is the first value to equal $x_K$, but now $i\leq K$ and the independence of $k_*$ is less clear. Let $k_i$ be such that $i=K+1-k_i$. We will need the following observations about $s(k)$; If $x_{K+1-k}=x_{K+1-(k+1)}$ then $s(k)=s(k+1)$ so we always have \begin{equation}\label{inh}x_{K+1-k_*}<x_{K+1-(k_*+1)}=x_{K-k_*}.\end{equation} Since $x\not \in P_K$, we also have $s_x(1)>0$. Combined this gives $s_x(k_i)=s_x(1)>0$ and hence $k_*\geq k_i$. If we now consider $s_{x(t)}(k)$ as functions of $t$, the inequality $s_{x(t)}(k_i)>0$ is stable with respect to small perturbations. On the other hand, the values of $s_{x(t)}(k)$ for $k>k_i$ are unaffected by small values of $t$ (they cancel out in the sum of \eqref{lust}), and so we conclude that $k_*$ is unaffected by small values of $t$. It follows that both terms depending on $t$ in $ x(t)$ have indices beyond $K-k_*$, which precisely as before yields that \eqref{po0} holds, a contradiction.

To sum up, we have so far shown that any element $x\in G_{K+1}\setminus P_K$ necessarily satisfies $|\tilde x_{K+1}|<R$ and $|\tilde x_n|=0$. As grande finale we will now show that this is impossible. Let $j$ be such that $x_j=0$ and pick $i$ such that $|x_i|\leq |{x}_K|$ and $\scal{a_i,a_j}\neq 0$. That this can be done follows from the basic fact that $m+1$ non-zero vectors in $\R^m$ can not be mutually orthogonal (suppose for the moment that no $a_i$ is identically 0). Since $x_j=0$, it is no restriction to assume that $\scal{a_i,a_j}> 0$, which we do for simplicity. Consider again $x(t)=x+t e_i- te_j$. The previous analysis can now be repeated without modification, to conclude that \eqref{po0} holds whether $i>K$ or not. But in this case \eqref{po0} has a strictly negative value, which contradicts that $x$ is in $G$ to begin with. In the case when one $a_i=0$, we have $\|a_i-a_j\|\leq 1$ for any other $a_j$, which also yields a contradiction in \eqref{po0}.

We can finally conclude that any minimizer of $\ksir$ in $[-R,R^n]$ is in $P_K$ and thus also a minimizer of $\ksi$. Since $R$ could be arbitrarily large, the conclusion holds also in $\R^n$. The set of global minimizers of $\ksir$ is thus closed and non-empty. However, the remaining argument becomes easier if we keep $R$ fixed where it is for a while longer.

Now consider a path-connected component $H$ of the set of global minimizers in $[-R,R]^n$. Repeating the entire above argument, we see that $P_K\cap H\neq\emptyset$. Assume now that it contains points that are not in $P_K$. Since $\sum_{j=K+1}^n |\tilde x_j|$ is a continuous function on $H$ which is 0 at $P_K$, there are points in $H$ with arbitrarily small quotient $(\sum_{j=K+1}^n|\tilde x_j|)/{|\tilde x_1|}$. Recall that we have ruled out the case $0\in H$ early on in the proof, so the quotient is a continuous function on $H$. Let $I$ be a level set of this function. We repeat the construction of sets $I_n\supset I_{n-1}\supset \ldots I_{K+1}$ precisely as we did with $G$. Pick a concrete $x\in I_{K+1}$, and as before it is no restriction to assume that $x=|\tilde x|$. As before we see that it is impossible to have $ x_n=0$, and as before we can pick $i,j$ such that $\scal{a_i,a_j}\geq 0$ where $i,j>K$. We define $x(t)$ via \eqref{function} and establish as before that the \eqref{po0} must hold, whereby we get that $x(t)\in I_{K+1}$ for small values of $t$, and this contradicts how the sets $I_1,\ldots, I_K$ were chosen.

By this we get that all global minimizers of $\ksir$ in $[-R,R]^n$ must lie in $P_K$, and since $R$ can be arbitrarily large, the proof about global minimizers is complete.

Finally if we assume that $A$ is strictly $K$-feasible and that $x$ is a local minimizer, then we can always find $i,j$ such that \eqref{po0} holds, which is a contradiction since  $-4+2\|a_i-a_j\|^2<0$ in this case.

\end{proof}

\subsection{On the uniqueness of sparse stationary points}

We now give a condition, similar to \eqref{e4} in Section \ref{erai}, to ensure that a sparse stationary point is unique, in the sense that other stationary points must have higher cardinality.

\begin{theorem}\label{thm:statpoint:vecfix}
Let $x'$ be a stationary point of $\ksir$ with cardinality $K$, let $z'$ be given by \eqref{y}, and assume that
\begin{equation}\label{e4fix}|\tilde z'_{K+1}|<(2\beta_{2K}^2-1)|\tilde z'_{K}|.\end{equation}
If $x''$ is another stationary point of $\ksir$ then $\card(x'') > K$.
\end{theorem}

Again, we allow $\beta_{2K}>1$ in the above theorem, in which case the condition on $z$ is automatically satisfied. We begin with a lemma. Recall $\G$ given by \eqref{gdef}, i.e.~$\frac{1}{2}\Q_2(\iota_{P_K})(x)+\frac{1}{2}\fro{x}$ in the present case. We need an expression for $\partial\G(x)$ for $x\in P_K$.

\begin{lemma}\label{sun}
If $x\in P_K$ then $z\in\partial\G(x)$ if and only if $\tilde z_j=\tilde x_j$ for $j=1,\ldots,K$ and $\tilde z_j\in |\tilde x_K|\D $ for $j>K$.
\end{lemma}
\begin{proof}
Since $\Q_2(\iota_{P_K})+\fro{x}$ is the l.s.c. convex envelope of $\iota_{P_K}+\fro{x}$, we have that $\G(x)=\frac{1}{2}\Q_2(\iota_{P_K})+\frac{1}{2}\fro{x}$ is the double Fenchel conjugate of $\frac{1}{2}\iota_{P_K}+\frac{1}{2}\fro{x}$. The Fenchel conjugate of the latter is easily computed to $$\G^*(y)=\frac{1}{2}\sum_{j=1}^K |\tilde y_j|^2.$$ By the well-known identity $z\in\partial \G(x)\Leftrightarrow x\in\partial \G^*(z)$ (see e.g. Proposition 16.9 in \cite{bauschke2017convex}) we have $z\in\partial\G(x)$ if and only if \begin{equation}\label{t6}z=\argmax_z \re\scal{x,z}-\frac{1}{2}\sum_{j=1}^K |\tilde z_j|^2.\end{equation}
By standard results on reordering of sequences (see e.g.~Ch.~1 in \cite{simon2005trace}), this implies that the reordering of $z$ to $\tilde z$ can be chosen identical to that of $x$, which implies that $\scal{x,z}=\scal{\tilde x,\tilde z}$. Combined with $\tilde{x}_j=0$ for $j>K$, we see that \eqref{t6} turns into \begin{equation}\label{t7}z=\frac{1}{2}\argmax_z-\sum_{j=1}^K |\tilde x_j-\tilde z_j|^2.\end{equation} The lemma now easily follows.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:statpoint:vecfix}.]
If $\card (x'')\leq K$ we clearly have $x''-x'\in P_{2K}$ and both $z'$ and $z''$ have the structure stipulated in Lemma \ref{sun}. Let $I'=\supp x'$ and $I''=\supp x''$. Then $\re\scal{z''-z',x''-x'}$ can be written
\begin{equation}
\re\left(\sum_{\footnotesize
\begin{array}{c}
i \in I' \\
i \in I''\end{array}}
|x_i''-x_i'|^2 +
\sum_{\footnotesize
\begin{array}{c}
i \in I' \\
i \notin I''\end{array}}
(x_i'-z_i'')\overline{x_i'} +
\sum_{\footnotesize
\begin{array}{c}
i \notin I' \\
i \in I''\end{array}}
(x_i''-z_i')\overline{x_i''}\right).
\label{eq:sum1}
\end{equation}
As before we want to reach a contradiction to Proposition \ref{thm:statpoint}, i.e.~we want to prove $\re\scal{z''-z',x''-x'}>(1-\beta_{2K}^2)\|x''-x'\|_2^2$. Note that
\begin{equation}\label{gr2}
\|x''-x'\|^2=\sum_{\footnotesize
\begin{array}{c}
i \in I' \\
i \in I''\end{array}}
|x_i''-x_i'|^2 +
\sum_{\footnotesize
\begin{array}{c}
i \in I' \\
i \notin I''\end{array}}
|x_i'|^2 +
\sum_{\footnotesize
\begin{array}{c}
i \notin I' \\
i \in I''\end{array}}
|x_{i}''|^{2},
\end{equation}
that the first term in \eqref{eq:sum1} and \eqref{gr2} are the same, and that $\beta_{2K}>0$. Since the second and third sums have the same number of terms it suffices to show that
\begin{equation}
\re (x_i'-z_i'')\overline{x_i'} + (x_j''-z_j')\overline{x_j''} > (1-\beta_{2K}^2)(|x_i'|^2 + |x_j''|^{ 2}),
\label{eq:twoterms}
\end{equation}
for any pair $i\in I'$, $i\notin I''$ and $j \notin I'$, $j \in I''$. This in turn will follow upon showing that
$$|z_i''| |x_i'| + |z_j'| |x_j''| < \beta_{2K}^2(|x_i'|^2 + |x_j''|^{ 2}).$$
By Lemma \ref{sun} it is easy to see that $|z_i''|\leq |z_j''|=|x_j''|$ and by assumption we also have $|z_j'|< (2\beta_{2K}^2-1)| z'_{i}|=(2\beta_{2K}^2-1)| x'_{i}|$. Thus $$|z_i''| |x_i'| + |z_j'| |x_j''| <  |x_j''||x_i'| + (2\beta_{2K}^2-1)| x'_{i}| |x_j''|=2\beta_{2K}^2| x'_{i}| |x_j''|\leq \beta_{2K}^2(|x_i'|^2 + |x_j''|^{ 2}),$$
as desired.
\end{proof}

\iffalse
For later use in [..], we record that we have shown the following result. \begin{corollary}\label{corbor1}
Let $z'$ satisfy $2z'\in\partial \G(x')$ and
\begin{equation*}|\tilde z'_{K+1}|<(2\lambda^2-1)|\tilde z'_{K}|.\end{equation*}
If $2z''\in\partial \G(x'')$, then $\re\scal{z''-z',x''-x'}>(1-\lambda^2)\|x''-x'\|^2$.
\end{corollary}
\fi

\subsection{Conditions on global minimality.}
The statements in this section are actually a bit stronger than the corresponding ones in Section  \ref{erai1}.

\begin{theorem}\label{thm:globalpoint2f}
Let $A$ be $K$-feasible and let $x'\in P_K$ be a stationary point of $\ksir$. Let $z'$ be given by \eqref{y} and assume that \eqref{e4fix} applies. Then $x'$ is a unique global minimizer of $\ksi$ and $\ksir$. If $A$ is strictly $K$-feasible, then there are no other local minimizers either.
\end{theorem}
\begin{proof}
By Theorem \ref{celok6} there exists $x''\in P_K$ which is a global minimizer for both $\ksi$ and $\ksir$. If $x'\neq x''$ this would contradict Theorem \ref{thm:statpoint:vecfix}. If in addition $A$ is strictly $K$-feasible, then Theorem \ref{celok6} says that any local minimizer is a stationary point in $P_K$, which is impossible by Theorem \ref{thm:statpoint:vecfix}.
\end{proof}

\subsection{Noisy data.}
We now assume that $b$ is of the form $Ax_0+\ep$ where $\ep$ is noise and $x_0$ is sparse. More precisely we set $S=\supp x_0$ where we assume that $\#S=K$.
Let $A_S$ denote the matrix obtained from $A$ by setting columns outside of $S$ to $0$. By minor modifications of the proof of Proposition \ref{p1} we obtain.

\begin{proposition}\label{p1f}
Let $A$ satisfy $\|A\|_{\infty,col}\leq 1$. If $|x_{0,j}|>\para{1+\frac{1}{\beta_K}}\|\ep\|$ for all $j\in S$ then the oracle solution $x'=x_S$ is a strict local minimizer of $\ksir$ with $\supp (x')=\supp (x_0)$. This also satisfies $|x'_j|>\|\epsilon\|$, $j\in S$, $\|Ax'-b\|\leq \|\epsilon\|$ and $$\|x'-x_0\|\leq \frac{\|\ep\|}{\beta_K}.$$
\end{proposition}

\begin{proof}
We assume for simplicity that we work over $\R$, and as in Proposition \ref{p1} we let $x'$ be the oracle solution. All estimates of Proposition \ref{p1} go through with minor modifications, for example \eqref{sofg} is replaced by \begin{equation}\label{hy}|x_{j}'|\geq |x_{0,j}|-|\de_j|>|x_{0,j}|-\frac{\|\ep\|}{\beta_K},\quad j\in S\end{equation} which shows that $\supp (x')=\supp (x_0)$ as well as $|x'_j|>\|\epsilon\|$ for $j\in S$.
The only real difference is the proof that $x'$ is a local minimizer of $\ksir$, so we consider $\ksir(x'+v)$ where as usual we can assume that $x'=|\tilde x'|$. Since $x'$ solves the least squares problem posed initially, the vector $A_S^*(Ax'-b)=A_S^*(A_Sx'-b)$ must be 0, and so \begin{equation*}\ksir(x'+v)=\Q_2(\iota_{P_K})(x'+v)+2\sum_{j=K+1}^n v_j\scal{a_j,Ax'-b} +\|Av\|^2+\ksir(x').\end{equation*} Let $k_1$ be such that $x_{K+1-k_1}=x_K$ but $x_{K-k_1}>x_K$, and note that $k_*$ will depend on $v$ but will always satisfy $k_*\leq k_1$. With this in mind $\Q_2(\iota_{P_K})(x'+v)$ becomes $$\frac{1}{k_*}\left(k_*x_K+\sum_{j=K-k_*+1}^K v_j+\sum_{j=K+1}^n|v_j|\right)^2-\sum_{j=K-k_*+1}^K(x_K+v_j)^2-\sum_{j=K+1}^n v_j^2.$$ Upon inspection there is a lot of cancelation and the expression reduces to
$2x_K\sum_{j=K+1}^n|v_j|$ plus quadratic terms in $v$.
Returning to the expression for $\ksir(x'+v)$ and collecting all quadratic contributions from $v$ in a term $q(v)$, we see that $\ksir(x'+v)-\ksi(x')$ equals
\begin{equation*}2x_K\left(\sum_{j=K+1}^n|v_j|\right)+2\left(\sum_{j=K+1}^n v_j\scal{a_j,Ax'-b}\right) +q(v).\end{equation*}
Since $|\scal{a_j,Ax'-b}|\leq\|\epsilon\|$ and $x_K>\|\epsilon\|$, it is easy to see that there exist some constant $\rho>0$ such that \begin{equation*}2x_K\left(\sum_{j=K+1}^n|v_j|\right)+2\left(\sum_{j=K+1}^n v_j\scal{a_j,Ax'-b}\right)\geq\rho\sqrt{\sum_{j=K+1}^nv_j^2}\end{equation*} near $0$. As in the proof of Proposition \ref{p1} we conclude that we must have $\sum_{j=K+1}^nv_j^2=0$ in order for $\ksir(x'+v)\leq \ksir(x')$ to be possible. However, for $v$ with $\supp v\subset S,$ $\Q_2(\iota_{P_K})(x'+v)=0$ and so $$\ksir(x'+v)=\|A(x'+v)-b\|^2\geq \|Ax'-b\|^2=\ksir(x'),$$ and the proof is complete.

\end{proof}

To go from saying that $x'$ is a strict local minimizer to saying unique global minimizer is now a short step.

\begin{theorem}\label{cor:dogadgetf}
Let $A$ be $K$-feasible and $\beta_{2K}>1/\sqrt{2}$. If $$|x_{0,j}|>\para{\frac{1}{2\beta_{2K}^2-1}+\frac{1}{\beta_K}}\|\ep\|,\quad j\in S$$ then the oracle solution $x'$ in the above proposition is a global minimum of $\ksi$ and $\ksir$. Moreover, if $A$ is strictly $K$-feasible then $\ksir$ has no other local minimizers.
\end{theorem}
\begin{proof}
Proposition \ref{p1f} clearly applies and  ensures that $x'$ is a local minimizer. We now check that \eqref{e4fix} applies for $z'$ given by \eqref{y}, i.e. we want to check that $|\tilde z'_{K+1}|<(2\beta_{2K}^2-1)|\tilde z'_K|$. Note that $|\tilde z'_{K+1}|\leq\|\ep\|$ by the same estimate as \eqref{o0}. Moreover, since $z'\in\partial \G(x')$, Lemma \ref{sun} implies that it suffices to show that $\|\ep\|<(2\beta_{2K}^2-1)|\tilde x'_K|$, which by \eqref{hy} follows if
$$\|\ep\|<(2\beta_{2K}^2-1)\para{|\tilde x_{0,K}|-\frac{\|\ep\|}{\beta_K}}$$ which easily is seen to be equivalent with the condition in the statement. The desired conclusions now follow by Theorem \ref{thm:globalpoint2f}.
\end{proof}

\bibliographystyle{plain}
\bibliography{newlib}
\end{document}

config: arxiv


text:
{\bf Problem.} In the diagram, point $E$ lies on line segment $AB$, and triangles $AED$ and $BEC$ are isosceles. Also, $\angle DEC$ is twice $\angle ADE$. What is the measure of $\angle EBC$ in degrees? [asy]
import olympiad;
import math;

size(7cm);

// Draw triangles
pair a = (-2 * Cos(70), 0);
pair b = (1, 0);
pair c = dir(30);
pair d = dir(110);
pair e = (0, 0);
draw(a--d--e--cycle);
draw(e--b--c--cycle);

// Labels
label("$A$", a, W); label("$B$", b, E);
label("$C$", c, N); label("$D$", d, N);
label("$E$", e, S); label("$70^\circ$", a, 2 * NE+ 0.5 * E);

// Ticks
add(pathticks(a--d, s=2));
add(pathticks(d--e, s=2));
add(pathticks(e--c, 2, spacing=0.7, s=2));
add(pathticks(e--b, 2, spacing=0.7, s=2));
[/asy]
{\bf Level.} Level 1
{\bf Type.} Geometry
{\bf Solution.} Since $\triangle ADE$ is isosceles, then $\angle AED=\angle EAD=70^\circ$.

Since the angles in $\triangle ADE$ add to $180^\circ$, then $\angle ADE = 180^\circ - 2(70^\circ) = 40^\circ$.

Since $\angle DEC=2(\angle ADE)$, then $\angle DEC = 2(40^\circ)=80^\circ$.

Since $AEB$ is a straight line, then $\angle CEB = 180^\circ - 80^\circ - 70^\circ = 30^\circ$.

Since $\triangle EBC$ is isosceles, then $\angle ECB=\angle EBC$.

Thus, in $\triangle EBC$, $30^\circ + 2(\angle EBC)=180^\circ$ or $2(\angle EBC)=150^\circ$ or $\angle EBC=\boxed{75^\circ}$.

set_name: MATH


TITLE: How to bound $\sum_{\ell^2 + m^2 \leq y } \tau(\ell^2 + m^2)$?
QUESTION [2 upvotes]: Let $\tau$ be the divisor function. I would like to know how I can obtain
$$
\sum_{\ell^2 + m^2 \leq y  } \tau(\ell^2 + m^2) \ll y \log y.
$$
Any comments would be appreciated. Thank you!

REPLY [5 votes]: Here is a sketch. By multiplicativity,
$$\sum_{n = 1}^{\infty} \frac{\tau(n) \sum_{d \mid n} \chi_4(d)}{n^s} = \prod_p \sum_{r = 0}^{\infty} \frac{\tau(p^r) \sum_{d \mid p^r} \chi_4(d)}{p^{rs}}.$$
We have that $\tau(p^r) = r + 1$, and if $p \equiv 1 \pmod{4}$, then $\sum_{d \mid p^r} \chi_4(d) = r + 1$, while if $p \equiv 3 \pmod{4}$, then $\sum_{d \mid p^r} \chi_4(d) = 1$ if $r$ is even and $\sum_{d \mid p^r} \chi_4(d) = 0$ if $r$ is odd. Thus this is equal to
$$\prod_{p \equiv 1 \pmod{4}} \sum_{r = 0}^{\infty} (r + 1)^2 p^{-rs} \prod_{p \equiv 3 \pmod{4}} \sum_{\substack{r = 0 \\ r \equiv 0 \pmod{2}}}^{\infty} (r + 1) p^{-rs}.$$
By evaluating these geometric series,
$$\sum_{r = 0}^{\infty} (r + 1)^2 p^{-rs} = \frac{1 - p^{-2s}}{(1 - p^{-s})^4} = \frac{1 - \chi_4(p) p^{-2s}}{(1 - p^{-s})^2 (1 - \chi_4(p) p^{-s})^2},$$
and
$$\sum_{\substack{r = 0 \\ r \equiv 0 \pmod{2}}}^{\infty} (r + 1) p^{-rs} = \frac{1 + p^{-2s}}{(1 - p^{-s})^2 (1 + p^{-s})^2} = \frac{1 - \chi_4(p) p^{-2s}}{(1 - p^{-s})^2 (1 - \chi_4(p) p^{-s})^2}.$$
So
$$\sum_{n = 1}^{\infty} \frac{\tau(n) \sum_{d \mid n} \chi_4(d)}{n^s} = \prod_p \frac{1 - \chi_4(p) p^{-2s}}{(1 - p^{-s})^2 (1 - \chi_4(p) p^{-s})^2} = \frac{\zeta(s)^2 L(s,\chi_4)^2}{L(2s,\chi_4)}.$$
So this has a double pole at $s = 1$ due to the pole of $\zeta(s)$, whereas $L(s,\chi_4)$ is holomorphic for $\Re(s) \geq 1$. Now any Tauberian theorem will do the job, or more generally one could use Perron's formula.


TITLE: Tangent of a parameterized curve and the derivative of a function
QUESTION [0 upvotes]: A parametrized curve is a function $\gamma : (\alpha,\beta)\to \mathbb R^n$.
The parametrized curve for a straight line with slope $m$ passing through origin is $\gamma(\alpha,\beta)={\{(t,mt)}\}$ where $t\in(\alpha,\beta)$
$\dot\gamma(t)=(1,m)$
$||\dot\gamma||=\sqrt{1+m^2}$
If we see the equation $y=mx$ the image of the set of points follow this equation also represent the straight line curve.
Also, $\frac{dy}{dx}=m$
Basically, $||\dot\gamma||=\sqrt{1+m^2}$ is the magnitude of speed with which the point travels.
I have two questions-

The question is that what does $\frac{dy}{dx}=m$ represents? As it also represents the rate at which y changes with x. Then how it is different from $||\dot\gamma||=\sqrt{1+m^2}$.
Basically what is the difference between $m$ and $||\dot\gamma||$? Why there values are different?
I want to know what is the difference between $y=mx$ and $\gamma(t)$ if $t\in(-\infty,\infty)$?

I have studied about only real analysis and basic mathematics till. So please explain accordingly.

REPLY [0 votes]: This is a consequence of Pythagoras. Draw a triangle of base $1$ and height $m$ equal to the slope. $\sqrt{1+m^2}$ is the hypothenuses.

There is no difference (but $\gamma$ is parameterized).


TITLE: Subtraction of inequalities
QUESTION [10 upvotes]: Suppose I have two inequalities:
$$k_1 \leq a$$
$$k_2 \leq b$$
where $k_1,k_2,a,b$ are all positive numbers
I know that that summation of them can be written as:
$$k_1+k_2 \leq a+b$$
But I want to find $$k_1-k_2 \leq ?$$ or $$? \leq k_1-k_2$$
Is there any way to solve this problem?

REPLY [0 votes]: Note that your property of summing inequalities for positive numbers can immediately be extended to signed numbers.

Indeed assuming $\begin{cases} k_1\le a\\k_2\le b\end{cases}$ then we have $\begin{cases} a-k_1\ge 0\\b-k_2\ge 0\end{cases}$ which are positive numbers.
Their sum is then positive $(a-k_1)+(b-k_2)\ge 0\iff (a+b)-(k_1+k_2)\ge 0$
Once rearranged it gives $$k_1+k_2\le a+b$$ independently of the signs of
$a,b,k_1,k_2$

Now the inequalities $\begin{cases} k_1\le a\\k_2\le b\end{cases}$  with positive numbers are in fact $\begin{cases} 0\le k_1\le a\\0\le k_2\le b\end{cases}$

We can invert the first one to get $\begin{cases} -a\le -k_1\le 0\\0\le k_2\le b\end{cases}$
Now summing all inequalities like we have seen in first point gives: $-a+0\le -k_1+k_2\le b+0$
Or simply $$-a\le k_2-k_1\le b$$


TITLE: A mean related to a continuous random variable
QUESTION [0 upvotes]: We are filling some liquid in multiple containers. The volume poured is uniformly distributed between 5.1 and 5.7 deciliters. Every centiliter costs 0.01 dollar.
Knowing that any centiliter added beyond 5.5 deciliters represents an extra cost for the producer, what is the mean of this extra cost?

I am not sure about how to approach this.
Since the volume is uniformly distributed, the mean volume is $(5.7+5.1)/2=5.4$, which is less than $5.5$. From this, I could say that, on average, the producer won't spend any extra dollars.
But then I thought that maybe I should interpret this as the average if we only consider the cases where the volume is more than $5.5$, so that my random variable is now $5.5\leq X\leq 5.7$.
If so, my new mean is $5.6$, which is just one centiliter above the lower-bound volume for there being an extra cost, resulting in a mean of $0.01$$.
Or maybe $\int_{5.5}^{5.7}\left[0.1(x-5.5)\right]f(x)dx$, where $f(x)$ is the pdf?

REPLY [1 votes]: When a container is filled in such a way that the volume poured does not exceed $5.5$ deciliters, there is no extra cost incurred.  When the volume poured does exceed $5.5$ deciliters, there is an extra cost, which is proportional to the amount of volume above $5.5$.
Your misunderstanding is that somehow, containers whose volume poured is below $5.5$ can compensate for the extra cost incurred from those containers where the volume poured is above $5.5$.  For instance, if only two containers are filled and one is filled to $5.1$ deciliters and the second is filled to $5.7$, the savings of the first container does not cancel out the extra cost of the second, which is still incurred even though the overall cost may still be acceptable.
Another way to think about it is that the producer would have filled the first container to $5.1$ anyway.  The extra cost is conceptualized as answering the question of, "if every container could have been filled so as to guarantee none has more than $5.5$ deciliters, how much money could have been saved?"
With this in mind, we see that the unconditional mean fill volume is not an indicator of the extra cost.  If $X$ is the random fill volume, then we are given $$X \sim \operatorname{Uniform}(5.1, 5.7).$$  The extra cost random variable is $$Y = 0.1 \min(X - 5.5, 0) = \begin{cases} 0, & 5.1 \le X \le 5.5 \\ (0.1)(X - 5.5), & 5.5 < X \le 5.7. \end{cases}$$  You want to compute $$\operatorname{E}[Y \mid X > 5.5] = 0.1 \operatorname{E}[X - 5.5 \mid X > 5.5] = 0.1 ( \operatorname{E}[X \mid X > 5.5] - 5.5 ).$$  Note that the extra cost of $0.01$ dollar per centiliter equals $0.1$ dollar per deciliter, which explains the factor of $0.1$.