Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It is known that given corrupt measurements $y = Af+e \in \mathbb{R}^m$ with $f \in \mathbb{R}^n$ and $\|f\|_0 < m < n$, one can recover $f$ exactly by solving a convex optimization problem. What if $f$ is instead a square matrix? Can we recover a matrix from corrupt measurements instead of just a vector?

share|improve this question
Isn't a matrix just a special case of a vector? That is, can't you "flatten" an $n\times n$ matrix into a vector in $\mathbb{R}^{n^2}$ and then solve the problem by the usual means? –  Noah Stein Nov 23 '11 at 3:00
I'm not sure I agree with the assertion in the first sentence. It seems to depend strongly on the nature of corruption, and on the precision of measurements. –  S. Carnahan Nov 23 '11 at 5:31
See epubs.siam.org/doi/abs/10.1137/070697835 –  rodms Jun 5 '14 at 21:19

1 Answer 1

First, I emphasize S. Carnahan's comment: Exact recovery from noisy measurements is not that simple. "Exact recovery" usually means "recovery of the exact support of $f$". Moreover, sparsity assumptions for $f$ and special assumptions for $A$ and the size of $e$ are needed.

To address your question: This again depends on a lot of things. Of course you can view this as $n$ multiple instances of the original problem and basically use the previous theory. Other structural assumption lead to other results (e.g. having a "joint sparsity pattern in the columns of $f$"). Buzzwords here are "joint sparsity" or "multiple measurement vectors".

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.