\section{Compressed sensing for sparse matrices}

Once a sparse representation for the matrix is known, the numerical core of our method for the fast computation of matrices is the application of compressed sensing to calculate sparse matrices without knowing \textit{a priori} where the non-zero elements are located. Related work has been presented in the field of compressive principal component pursuit~\cite{Baraniuk2011,Candes2011,Zhou2010,Wright2013}, which focuses on reconstructing matrices that are the sum of a low-rank component and a sparse component.  Our work instead outlines a general procedure for reconstructing any sparse matrix by measuring it in a different basis.

Suppose we wish to recover a \(N \times N\) matrix \(A\) known to be sparse in a particular orthonormal basis \(\{\psi_i\}\) (for simplicity we restrict ourselves to square matrices and orthonormal bases).  Without any prior knowledge of where the \(S\) non-zero elements of \(A\) are located, it might appear that we need to calculate all \(N^2\) elements, but this is not the case.

In a different orthonormal basis \(\{\phi_i\}\), the matrix \(A\) has a second representation \(B\) given by 
\begin{equation}
\label{eq:cob_matrix}
B = PAP^{T}\ ,
\end{equation}
where \(P\) is the orthogonal change-of-basis matrix from the basis \(\{\psi_i\}\) to the basis \(\{\phi_i\}\).  Note that in general \(B\) is not sparse.

If we regard \(A\) and \(B\) as \(N^2\)-element \emph{vectors}, it is easy to see that the change-of-basis transformation from \(A\) to \(B\) given by eq.~\ref{eq:cob_matrix} is linear.  This fact enables us to use the machinery of compressed sensing to reconstruct the full matrix \(A\) by sampling only \textit{some} of the entries of \(B\). The reconstruction is done by solving the basis pursuit (BP) problem \cite{Berg2008},
%
\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{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 entries in matrix \(B\).  This approach to matrix reconstruction is illustrated in Fig.~\ref{fig:NumericsScheme}.
  