Welcome to MathOverflow

Question

0

1

It is known that given corrupt measurements $y = Af+e$ one can recover an input vector $f \in \textbf{R}^n$ 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?

flag	asked Nov 23 2011 at 2:52 Richard 1

7

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 2011 at 3:00

1

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 2011 at 5:31

Dirk · Answer 1 · 2011-11-23 07:25:57Z UTC

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".

Recovering a matrix instead of a vector

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.