Jaya Narasimhan

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2016-79
May 13, 2016

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2016/EECS-2016-79.pdf

In this report we lower the bounds on the number of required sampled entries for reconstructing low- rank positive semidefinite matrices through nuclear norm minimization. We show for an n × n matrix of rank r only O(r n logn loglogn) samped entries are needed to complete the matrix as compared to previous work’s O(r n log^2 n) entries. We obtain this result by using rejection sampling when constructing a dual variable certificate.

Advisor: Satish Rao

BibTeX citation:

@mastersthesis{Narasimhan:EECS-2016-79,
    Author = {Narasimhan, Jaya},
    Title = {Low-Rank Matrix Completion for Positive Semidefinite Matrices},
    School = {EECS Department, University of California, Berkeley},
    Year = {2016},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2016/EECS-2016-79.html},
    Number = {UCB/EECS-2016-79},
    Abstract = {In this report we lower the bounds on the number of required sampled entries for reconstructing low- rank positive semidefinite matrices through nuclear norm minimization. We show for an n × n matrix of rank r only O(r n logn loglogn) samped entries are needed to complete the matrix as compared to previous work’s O(r n log^2 n) entries. We obtain this result by using rejection sampling when constructing a dual variable certificate.}
}

EndNote citation:

%0 Thesis
%A Narasimhan, Jaya
%T Low-Rank Matrix Completion for Positive Semidefinite Matrices
%I EECS Department, University of California, Berkeley
%D 2016
%8 May 13
%@ UCB/EECS-2016-79
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2016/EECS-2016-79.html
%F Narasimhan:EECS-2016-79