Asymptotic Convergence Rate of Alternating Minimization for Rank One Matrix Completion

• URL: http://arxiv.org/abs/2008.04988v1
• Date: Tue, 11 Aug 2020 19:56:35 GMT
• Title: Asymptotic Convergence Rate of Alternating Minimization for Rank One Matrix Completion
• Authors: Rui Liu and Alex Olshevsky
• Abstract summary: We study alternating minimization for completion in the simplest possible setting. We bound the convergence rate by the variational characterization of eigenvalues of a reversible consensus problem. This leads to an upper bound on the rate in terms of number of nodes as well as the largest degree of the graph of revealed entries.
• Score: 15.321579527891457
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study alternating minimization for matrix completion in the simplest possible setting: completing a rank-one matrix from a revealed subset of the entries. We bound the asymptotic convergence rate by the variational characterization of eigenvalues of a reversible consensus problem. This leads to a polynomial upper bound on the asymptotic rate in terms of number of nodes as well as the largest degree of the graph of revealed entries.

Related papers

• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling [10.824999179337558]
  We show that it is often better and sometimes optimal to run estimation algorithms on a smaller submatrix rather than the entire matrix. Our bounds characterize the hardness of estimating each entry as a function of the localized sampling probabilities.
  arXiv  Detail & Related papers  (2024-02-29T23:24:43Z)
• Complete Upper Bound Hierarchies for Spectral Minimum in Noncommutative Polynomial Optimization [1.6385815610837167]
  This work focuses on finding the spectral minimum of a noncommutative subject to a finite number of noncommutative constraints. The Navascu'es-Pironio-Ac'in hierarchy is the noncommutative analog of Lasserre's moment-sum of squares hierarchy. This paper derives complementary complete hierarchies of upper bounds for the spectral minimum.
  arXiv  Detail & Related papers  (2024-02-03T11:53:57Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization [16.325663190517773]
  We consider the asymmetric factorization problem under a natural non formulation with arbitrary overparamatrization. We produce the best low-rank approximation to the observed matrix.
  arXiv  Detail & Related papers  (2022-03-06T00:07:53Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Pure Exploration and Regret Minimization in Matching Bandits [19.205538784019936]
  We prove that it is possible to leverage a rank-1 assumption on the adjacency matrix to reduce the sample complexity. Finding an optimal matching in a weighted graph is a standard problem.
  arXiv  Detail & Related papers  (2021-07-31T12:37:51Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent [22.851500417035947]
  Factorization-based gradient descent is a scalable and efficient algorithm for solving the factorrank matrix completion. We show that gradient descent enjoys fast convergence to estimate a solution of the global nature problem.
  arXiv  Detail & Related papers  (2021-02-04T03:41:54Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  We study the problem of solving strongly convex and smooth unconstrained optimization problems using first-order algorithms. We devise a novel, referred to as Recursive One-Over-T SGD, based on an easily implementable, averaging of past gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an sense.
  arXiv  Detail & Related papers  (2020-08-28T14:46:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.