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.

Advisors: 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