Xavier Andrade edited Theory.tex  over 9 years ago

Commit id: 6b0a44909e78d7101b46970333767fbe1ffed825

deletions | additions      

       

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\).  Given the matrix \(P\) or equivalently the basis \(\{\phi_i\}\), compressed sensing allows to reconstruct the full matrix \(A\) sampling \texit{some} of the entries of \(B\). The reconstruction is done by solving the basis pursuit problem (BP),  \begin{align} \begin{equation}  \label{eq:bpdn}  \min_{A} ||A||_1 \quad \textrm{subject to} \quad (PAP^T)_{ij} = B_{ij}\quad \forall  \ i,j \in W \ ,  \end{align} \end{equation}  where the 1-norm is considered as a \emph{vector} norm  (\(||A||_1 = \sum_{i,j} \left|A_{ij}\right|\)), and \(W\) is a set of randomly chosen matrix elements. entries. The size of \(W\) is the number of matrix elements of \(B\) that we need to sample, and it will determine the success of the reconstruction.  One important requirement for compressed sensing is that the basis  $\{\psi_i\}$ for \(A\) and the basis $\{\phi_i\}$ for \(B\) should be  \begin{align} %  \begin{equation}  \label{eq:coherence}  \mu = \sqrt{N} \max_{i,j} \langle \psi_i | \phi_j \rangle  \end{align} \end{equation}  %  should be as \emph{small} as possible (in general \(\mu\) ranges from  1 to \(\sqrt{N}\)). Intuitively speaking, this incoherence condition  simply means that the change-of-basis matrix \(P\) should thoroughly