Convex Reconstruction of Structured Matrix Signals from Linear
  Measurements (I): Theoretical Results
  We investigate the problem of reconstructing n-by-n structured matrix signal
X via convex programming, where each column xj is a vector of s-sparsity and
all columns have the same l1-norm. The regularizer in use is matrix norm
|||X|||1=maxj|xj|1.The contribution in this paper has two parts. The first part
is about conditions for stability and robustness in signal reconstruction via
solving the convex programming from noise-free or noisy measurements.We
establish uniform sufficient conditions which are very close to necessary
conditions and non-uniform conditions are also discussed. Similar as the
traditional compressive sensing theory for reconstructing vector signals, a
related RIP condition is established. In addition, stronger conditions are
investigated to guarantee the reconstructed signal's support stability, sign
stability and approximation-error robustness. The second part is to establish
upper and lower bounds on number of measurements for robust reconstruction in
noise. We take the convex geometric approach in random measurement setting and
one of the critical ingredients in this approach is to estimate the related
widths bounds in case of Gaussian and non-Gaussian distributions. These bounds
are explicitly controlled by signal's structural parameters r and s which
determine matrix signal's column-wise sparsity and l1-column-flatness
respectively.
