A Caltech Library Service

Subspace Expanders and Matrix Rank Minimization

Oymak, Samet and Khajehnejad, Amin and Hassibi, Babak (2011) Subspace Expanders and Matrix Rank Minimization. In: 2011 IEEE International Symposium on Information Theory Proceedings. IEEE , Piscataway, NJ, pp. 2308-2312. ISBN 978-1-4577-0596-0.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 or Bernoulli 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×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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle Paper
Additional Information:© 2011 IEEE. Date of Current Version: 03 October 2011.
Subject Keywords:rank minimization, subspace expanders
Record Number:CaltechAUTHORS:20120406-111241824
Persistent URL:
Official Citation:Oymak, S.; Khajehnejad, A.; Hassibi, B.; , "Subspace expanders and matrix rank minimization," Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on , vol., no., pp.2308-2312, July 31 2011-Aug. 5 2011 doi: 10.1109/ISIT.2011.6033974 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:30014
Deposited By: Ruth Sustaita
Deposited On:06 Apr 2012 18:25
Last Modified:03 Oct 2019 03:46

Repository Staff Only: item control page