Moritz HardtPublicationsBlogTalksMoritz HardtI'm a research staff member in the theory group at IBM Research Almaden. I joined IBM Almaden after completing a PhD in Computer Science at Princeton University in 2011. My advisor was Boaz Barak.Research Interests:Algorithms, machine learning, social questions in computationRecent Activities:Visiting Scientist at the Simons Institute for Theoretical Computer Science (Fall 2013)STOC 2014: Program CommitteeFOCS 2013: Program CommitteeSTOC 2013: Program CommitteeICALP 2012: Program CommitteeSICOMP Special Issue for FOCS 2013: Co-EditorAddress:IBM Almaden Research Office B2 250 650 Harry Road, San Jose, CA 95120Office Phone: (408) 927 2694 Email: m(at)mrtz(dot)org Twitter: @mrtzBlog: Moody RdPublications (selected)See selectedpublications.Moritz HardtOn the Provable Convergence of AlternatingMinimization for Matrix CompletionManuscript. Invited abstract at ITA 2014Links: Full version (arXiv),Abstract:Alternating Minimization is a widely used and empirically successful framework for Matrix Completion and related low-rank optimization problems. We give anew algorithm based on Alternating Minimization that provably recovers anunknown low-rank matrix from a random subsample of its entries under astandard incoherence assumption while achieving a linear convergence rate. Compared to previous work our results reduce the provable sample complexityrequirements of the Alternating Minimization approach by at least a quarticfactor in the rank and the condition number of the unknown matrix. Theseimprovements apply when the matrix is exactly low-rank and when it isonly close to low-rank in the Frobenius norm.Underlying our work is a new robust convergence analysis of the well-knownSubspace Iteration algorithm for computing the dominant singular vectors of amatrix also known as the Power Method. This viewpoint leads to a conceptuallysimple understanding of Alternating Minimization that we exploit.Additionally, we contribute a new technique for controlling the coherence ofintermediate solutions arising in iterative algorithms. These techniques maybe of interest beyond their application here.Moritz HardtRobust Subspace Iteration and Privacy-Preserving Spectral AnalysisManuscript. Invited abstract at ALLERTON 2013Links: Full version (arXiv)Abstract:We provide a new robust convergence analysis of the well-known subspaceiteration algorithm for computing the dominant singular vectors of a matrix,also known as simultaneous iteration or power method.  Our resultcharacterizes the convergence behavior of the algorithm when a large amountnoise is introduced after each matrix-vector multiplication. While interestingin its own right, our main motivation comes from the problem ofprivacy-preserving spectral analysis where noise is added in order to achievethe privacy guarantee known as differential privacy. Our contributions hereare twofold:We give nearly tight worst-case bounds for the problem of computing adifferentially private low