  We consider the synthesis problem of Compressed Sensing - given s and an MXn
matrix A, extract from it an mXn submatrix A', certified to be s-good, with m
as small as possible. Starting from the verifiable sufficient conditions of
s-goodness, we express the synthesis problem as the problem of approximating a
given matrix by a matrix of specified low rank in the uniform norm. We propose
randomized algorithms for efficient construction of rank k approximation of
matrices of size mXn achieving accuracy bounds O(1)sqrt({ln(mn)/k) which hold
in expectation or with high probability. We also supply derandomized versions
of the approximation algorithms which does not require random sampling of
matrices and attains the same accuracy bounds. We further demonstrate that our
algorithms are optimal up to the logarithmic in m and n factor. We provide
preliminary numerical results on the performance of our algorithms for the
synthesis problem.
