Abstract: In this study, a group of sufficient conditions is established for reconstructing the structured matrix signal X=x₁, …, x_n with the column-wise sparsity and flatness features via convex programming, where each column xj is a vector of s-sparsity and all columns have the same value of l₁ norms. The regularizer in use is a matrix norm ‖|X|‖₁≡max_j|x_j|₁. The contributions have two parts: First, sufficient conditions are established for stability and robustness in signal reconstruction by solving the min-‖|·|‖₁ convex program from noise-free or noisy measurements. Second, fundamental lower bounds on the dimensions of the measurement space are established for correct reconstruction with high probability. The results are superior to those obtained by directly extending the vector signal's min-l₁ approach to the matrix signal's min-l₁ approach. Numerical simulations are presented. The investigated signal model appears in some emerging application fields, e.g., multiple-input and multiple-output and synthetic aperture radars with constant or slowly varying envelope waveforms. The work in this paper provides practical conditions to reconstruct such signals.