Rank minimization for subspace tracking from incomplete data

Morteza Mardani, Gonzalo Mateos, Georgios B Giannakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

Extracting latent low-dimensional structure from high-dimensional data is of paramount importance in timely inference tasks encountered with 'Big Data' analytics. However, increasingly noisy, heterogeneous, and incomplete datasets as well as the need for real-time processing pose major challenges towards achieving this goal. In this context, the fresh look advocated here permeates benefits from rank minimization to track low-dimensional subspaces from incomplete data. Leveraging the low-dimensionality of the subspace sought, a novel estimator is proposed based on an exponentially-weighted least-squares criterion regularized with the nuclear norm. After recasting the non-separable nuclear norm into a form amenable to online optimization, a real-time algorithm is developed and its convergence established under simplifying technical assumptions. The novel subspace tracker can asymptotically offer the well-documented performance guarantees of the batch nuclear-norm regularized estimator. Simulated tests with real Internet data confirm the efficacy of the proposed algorithm in tracking the traffic subspace, and its superior performance relative to state-of-the-art alternatives.

Original languageEnglish (US)
Title of host publication2013 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Proceedings
Pages5681-5685
Number of pages5
DOIs
StatePublished - Oct 18 2013
Event2013 38th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013 - Vancouver, BC, Canada
Duration: May 26 2013May 31 2013

Other

Other2013 38th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2013
CountryCanada
CityVancouver, BC
Period5/26/135/31/13

Keywords

  • Low rank
  • matrix completion
  • online algorithm

Fingerprint Dive into the research topics of 'Rank minimization for subspace tracking from incomplete data'. Together they form a unique fingerprint.

Cite this