Richard Guo edited subsection_Non_convex_optimization_formulation__.tex  over 8 years ago

Commit id: f7960fed80ff07d83e5e55aa132be582a6122313

deletions | additions      

       

Since $\mathbf{A_0}$ is complete, the row space of $\mathbf{Y}$ is equivalent to the row space of $\mathbf{X}_0$. By the result from \cite{spielman2013exact}, under the generative model, rows of $\mathbf{X}_0$ corresponds to the $n$ sparsest vectors in the row space. Once $\mathbf{X}_0$ is recovered, $\mathbf{A}_0$ could be solved from least square $\mathbf{A}_0 = \mathbf{Y} \mathbf{X}_0 (\mathbf{X}_0 \mathbf{X}_0^T)^{-1}$.   A straightforward formulation for recovering one row of $\mathbf{X}_0$  is \[ \min \| \mathbf{q}^{T} \mathbf{Y} \|_0 \quad s.t.\ \mathbf{q} \neq \mathbf{0}. \]  $\mathbf{X}_0$ can be recovered row by row by \textit{deflation}.  However, this is discontinuous and the scale of $\mathbf{q}$ is unidentifiable. The problem above is recast as  

Next, we summarize some of the key properties of this problem, which are later formalized by the paper.   \begin{enumerate}  \item The feasible region $\mathbf{q} \in \mathbb{S}^{n-1}$ is a sphere with $2n$ symmetric parts, sections,  corresponding to those centered around $\pm \mathbf{e}_i$ for $i=1,\cdots,n$. \item  \end{enumerate}