Xavier Andrade edited Theory.tex  over 9 years ago

Commit id: 48a147546c7b31d3d9a51df888a6ba517e823200

deletions | additions      

       

Suppose we wish to recover an \(N \times N\) matrix \(A\) known to be sparse in a particular orthonormal basis $\{\psi_i\}$(for simplicity we restrict ourselves to square matrices an orthonormal bases). Without no prior knowledge of where the \(S\) non-zero  entries of \(A\) are located, to recover the matrix we need to calculate all the elements of of the matrix.  \(\{\phi_i\}\). The matrices In a second basis \(\{\phi_i\}\), the matrix  \(A\) and has a second representation  \(B\) are related according to  the change-of-basis formula given by  \begin{align}  \label{eq:cob_matrix}  B = PAP^{T} PAP^{T}\ ,  \end{align}  where \(P\) is the orthogonal matrix that transforms any vector from  the basis $\{\psi_i\}$ to $\{\phi_i\}$. In general, \(B\) is not a sparse matrix.  If we regard \(A\) and \(B\) as \(N^2\)-element \emph{vectors}  formed by stacking the columns of the matrices, we can note that the change-of-basis  transformation between \(A\) and \(B\) given by eq.~(\ref{eq:cob_matrix}) is \emph{linear}. This fact enables us to use of the machinery of compressed sensing for the problem of determining \(A\).  The key point of eq.~(\ref{eq:cob_matrix}) is that Given  the entries of  that if we regard \(A\) and \(B\) as \(N^2\)-element \emph{vectors}  formed by stacking the columns of matrix \(P\) or equivalently  the matrices, the change-of-basis  transformation between \(A\) and \(B\) is \emph{linear}. This fact  enables basis \(\{\phi_i\}\), compressed sensing allows to reconstruct  the full use of the machinery matrix \(A\) sampling \texit{some}  ofcompressed sensing:  the entries of \(B\) may be undersampled at random, and \(A\) may be  recovered \(B\). The reconstruction is done  by solving the basis pursuit problem (BP), \begin{align}  \label{eq:bpdn}  \min_{A} ||A||_1 \quad \textrm{subject to} \quad PAP^T = B,