A research problem, in matrix completion
I’ve started a new research problem, this time to do with low rank matrix completion problems. The quintessential problem there is, you’re given a small set of measurements taken from some large matrix, which you know has low rank, and you’d like to use those measurements to determine what the matrix is. It’s like compressed sensing for matrices.
In general, the feasibility of exactly or closely recovering the matrix from the measurements, and how few measurements are effective, depends upon the measurement method. In particular, if the measurement method satisfies a rank analog of the Restricted Isometry Principle, one has reasonable recovery guarantees. Denote by 
the measurement function that maps a matrix to a vector of measurements. Considering the set of matrices as a trace Hilbert space, with the Frobenius norm, we say that satisfies the rank RIP if it is an isomorphism between the set of sufficiently low rank matrices and their image. The closeness of the RIP constants to unity measures how good the measurement method is.
In my case, the measurements are a random subset of inner products with a certain orthonormal basis for 
, where 
is a power of 2– this particular setup is, I think, motivated by the problem of using a few measurements to determine a quantum state. My goal is to show that the proposed measurement function satisfies the RIP.
Possibly relevant posts:
- A dictionary, or not? (1/27/2010)
- Numerical Rank (6/16/2008)
- Musings on the matrix problem (6/15/2006)