Allerton 2015 Paper Abstract

Close

Paper ThB5.2

Pimentel-Alarcon, Daniel Leonardo (University of Wisconsin-Madison), Boston, Nigel (University of Wisconsin - Madison), Nowak, Robert (University of Wisconsin, Madison)

A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion

Scheduled for presentation during the Regular Session "Sparse Signal Processing" (ThB5), Thursday, October 1, 2015, 10:50−11:10, Lower Level

53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on November 19, 2019

Keywords Sparse Data Analysis

Abstract

Low-rank matrix completion (LRMC) problems arise in a wide variety of applications. Previous theory mainly provides conditions for completion under missing-at-random samplings. This paper studies deterministic conditions for completion. An incomplete dxN matrix is finitely rank-r completable if there are at most finitely many rank-r matrices that agree with all its observed entries. Finite completability is the tipping point in LRMC, as a few additional samples of a finitely completable matrix guarantee its unique completability. The main contribution of this paper is a characterization of finitely completable observation sets. We use this characterization to derive sufficient deterministic sampling conditions for unique completability. We also show that under uniform random sampling schemes, these conditions are satisfied with high probability if O(max{r,log d}) entries per column are observed.

 

 

All Content © PaperCept, Inc..


This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2019 PaperCept, Inc.
Page generated 2019-11-19  13:05:59 PST  Terms of use