Emaan Hariri

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2022-33

May 1, 2022

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-33.pdf

In this report, we progress towards removing an extraneous condition imposed in previous sample complexity results for matrix completion via nuclear norm minimization. We build upon the sample complexity results of Candès and Recht (2009), Candès and Tao (2010), Gross (2011), and Recht (2011) which employ a dual certificate construction that, with high probability, guarantees the optimality of nuclear norm minimization. The aforementioned authors all make two assumptions in their analysis about the rank-$r$ target matrix $\mathbf{M} \in \R^{n \times n}$ with singular value decomposition $\mathbf{U \Sigma V^*}$ which we wish to recover. The first assumption, that $\mathbf{M}$ has \textit{coherence} bounded by $\mu_0$, was shown to be necessary by Candès and Tao (2010) and is preserved here. We aim, then, to remove the second assumption, that entries of $\mathbf{UV^*}$ are bounded in magnitude by $\sfrac{\mu_1 \sqrt{r}}{n}$, by improving on the analysis of Recht (2011). In particular, Recht (2011) constructs the dual via an iterative process wherein the approximation error is tracked using a residual matrix. Recht (2011) ensures the maximum entry of the residuals drops geometrically. Here, we track individual matrix entries and their respective columns and rows much more closely, rather than relying on a global bound. As a result, we demonstrate exact recovery of matrices is possible with $m \ge O(\mu_0 nr^{3/2}\beta \log^2 n)$ entries, with probability $1 - n^{-\Omega(\mathrm{poly}(\beta))}$ for $\beta > 0$ of our choosing. This represents an improvement by a factor of $O(\mu_0\sqrt{r})$ from $O(\mu_0^2nr^2 \beta \log^2 n)$, the best possible result from Recht (2011) when not relying on the bounded entry assumption.

Advisors: Satish Rao and Michael William Mahoney

---

BibTeX citation:

@mastersthesis{Hariri:EECS-2022-33,
    Author= {Hariri, Emaan},
    Title= {Improved Bounds for Incoherent Matrix Completion},
    School= {EECS Department, University of California, Berkeley},
    Year= {2022},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-33.html},
    Number= {UCB/EECS-2022-33},
    Abstract= {In this report, we progress towards removing an extraneous condition imposed in previous sample complexity results for matrix completion via nuclear norm minimization. We build upon the sample complexity results of Candès and Recht (2009), Candès and Tao (2010), Gross (2011), and Recht (2011) which employ a dual certificate construction that, with high probability, guarantees the optimality of nuclear norm minimization. The aforementioned authors all make two assumptions in their analysis about the rank-$r$ target matrix $\mathbf{M} \in \R^{n \times n}$ with singular value decomposition $\mathbf{U \Sigma V^*}$ which we wish to recover. The first assumption, that $\mathbf{M}$ has \textit{coherence} bounded by $\mu_0$, was shown to be necessary by Candès and Tao (2010) and is preserved here. We aim, then, to remove the second assumption, that entries of $\mathbf{UV^*}$ are bounded in magnitude by $\sfrac{\mu_1 \sqrt{r}}{n}$, by improving on the analysis of Recht (2011). In particular, Recht (2011) constructs the dual via an iterative process wherein the approximation error is tracked using a residual matrix. Recht (2011) ensures the maximum entry of the residuals drops geometrically. Here, we track individual matrix entries and their respective columns and rows much more closely, rather than relying on a global bound. As a result, we demonstrate exact recovery of matrices is possible with $m \ge O(\mu_0 nr^{3/2}\beta \log^2 n)$ entries, with probability $1 - n^{-\Omega(\mathrm{poly}(\beta))}$ for $\beta > 0$ of our choosing. This represents an improvement by a factor of $O(\mu_0\sqrt{r})$ from $O(\mu_0^2nr^2 \beta \log^2 n)$, the best possible result from Recht (2011) when not relying on the bounded entry assumption.},
}

EndNote citation:

%0 Thesis
%A Hariri, Emaan 
%T Improved Bounds for Incoherent Matrix Completion
%I EECS Department, University of California, Berkeley
%D 2022
%8 May 1
%@ UCB/EECS-2022-33
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-33.html
%F Hariri:EECS-2022-33