Subspace Expanders and Matrix Rank Minimization

Details Subspace Expanders and Matrix Rank Minimization Subspace Expanders and Matrix Rank Minimization

2011-02-19

arxiv.org/abs/1102.3947v1

Computer Science

Information Theory

Scientific paper

Matrix rank minimization (RM) problems recently gained extensive attention due to numerous applications in machine learning, system identification and graphical models. In RM problem, one aims to find the matrix with the lowest rank that satisfies a set of linear constraints. The existing algorithms include nuclear norm minimization (NNM) and singular value thresholding. Thus far, most of the attention has been on i.i.d. Gaussian measurement operators. In this work, we introduce a new class of measurement operators, and a novel recovery algorithm, which is notably faster than NNM. The proposed operators are based on what we refer to as subspace expanders, which are inspired by the well known expander graphs based measurement matrices in compressed sensing. We show that given an $n\times n$ PSD matrix of rank $r$, it can be uniquely recovered from a minimal sampling of $O(nr)$ measurements using the proposed structures, and the recovery algorithm can be cast as matrix inversion after a few initial processing steps.

Affiliated with

Also associated with

No associations

Rating

Subspace Expanders and Matrix Rank Minimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Subspace Expanders and Matrix Rank Minimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Subspace Expanders and Matrix Rank Minimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-159244