Jacob Sanders edited Numerical Foundation 2.tex  over 9 years ago

Commit id: 98c884568bf0188bd2e17f26a3d9f61e650c3052

deletions | additions      

       

The size of the set  \(W\), a number that we call \(M\), is the number of matrix elements of \(B\) that we need to sample and it  determines the quality of the reconstruction. reconstruction of \(A\).  From compressed sensing theory we can find a lower bound for \(M\), as a function of \(P\), \(S\) and \(N\). One important requirement for compressed sensing is that the basis $\{\psi_i\}$ \(\{\psi_i\}\)  for \(A\) and the basis $\{\phi_i\}$ \(\{\phi_i\}\)  for \(B\) should be \textit{incoherent}, meaning that the maximum overlap between any vector in the \(\{\psi_i\}\) and \(\{\psi_i\}\)  \begin{equation}  \label{eq:coherence}  \mu = \sqrt{N} \max_{i,j} \langle \psi_i | \phi_j \rangle  \end{equation}  should be as \emph{small} as possible (in general \(\mu\) ranges from 1 to \(\sqrt{N}\)). Intuitively speaking, Intuitively,  this incoherence conditionsimply  means that the change-of-basis matrix \(P\) should thoroughly scramble the entries of \(A\) to generate \(B\). It can be proven~\cite{Candes2006,Donoho2006,Candes2008} that the number of entries of \(B\) which must be measured in order to fully recover \(A\) by solving the BP problem in eq.~\ref{eq:bpdn} scales as  \begin{align}