  Compressed Sensing (CS) is an emerging field that enables reconstruction of a
sparse signal $x \in {\mathbb R} ^n$ that has only $k \ll n$ non-zero
coefficients from a small number $m \ll n$ of linear projections. The
projections are obtained by multiplying $x$ by a matrix $\Phi \in {\mathbb
R}^{m \times n}$ --- called a CS matrix --- where $k < m \ll n$. In this work,
we ask the following question: given the triplet $\{k, m, n \}$ that defines
the CS problem size, what are the deterministic limits on the performance of
the best CS matrix in ${\mathbb R}^{m \times n}$? We select Restricted Isometry
as the performance metric. We derive two deterministic converse bounds and one
deterministic achievable bound on the Restricted Isometry for matrices in
${\mathbb R}^{m \times n}$ in terms of $n$, $m$ and $k$. The first converse
bound (structural bound) is derived by exploiting the intricate relationships
between the singular values of sub-matrices and the complete matrix. The second
converse bound (packing bound) and the achievable bound (covering bound) are
derived by recognizing the equivalence of CS matrices to codes on Grassmannian
spaces. Simulations reveal that random Gaussian $\Phi$ provide far from optimal
performance. The derivation of the three bounds offers several new geometric
insights that relate optimal CS matrices to equi-angular tight frames, the
Welch bound, codes on Grassmannian spaces, and the Generalized Pythagorean
Theorem (GPT).
