Matrix Completion from General Deterministic Sampling Patterns

• URL: http://arxiv.org/abs/2306.02283v1
• Date: Sun, 4 Jun 2023 07:01:31 GMT
• Title: Matrix Completion from General Deterministic Sampling Patterns
• Authors: Hanbyul Lee, Rahul Mazumder, Qifan Song, Jean Honorio
• Abstract summary: We establish theoretical guarantee for the exact and approximate low-rank matrix completion problems. We show that the algorithm can be successful as the observation graph is well-connected and has similar node degrees.
• Score: 28.116011361245224
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most of the existing works on provable guarantees for low-rank matrix completion algorithms rely on some unrealistic assumptions such that matrix entries are sampled randomly or the sampling pattern has a specific structure. In this work, we establish theoretical guarantee for the exact and approximate low-rank matrix completion problems which can be applied to any deterministic sampling schemes. For this, we introduce a graph having observed entries as its edge set, and investigate its graph properties involving the performance of the standard constrained nuclear norm minimization algorithm. We theoretically and experimentally show that the algorithm can be successful as the observation graph is well-connected and has similar node degrees. Our result can be viewed as an extension of the works by Bhojanapalli and Jain [2014] and Burnwal and Vidyasagar [2020], in which the node degrees of the observation graph were assumed to be the same. In particular, our theory significantly improves their results when the underlying matrix is symmetric.

Related papers

• Low-rank Bayesian matrix completion via geodesic Hamiltonian Monte Carlo on Stiefel manifolds [0.18416014644193066]
  We present a new sampling-based approach for enabling efficient computation of low-rank Bayesian matrix completion. We show that our approach resolves the sampling difficulties encountered by standard Gibbs samplers for the common two-matrix factorization used in matrix completion. Numerical examples demonstrate superior sampling performance, including better mixing and faster convergence to a stationary distribution.
  arXiv  Detail & Related papers  (2024-10-27T03:12:53Z)
• Entry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flows [9.631640936820126]
  Matrix completion tackles the task of predicting missing values in a low-rank matrix based on a sparse set of observed entries. We introduce a matrix completion algorithm based on network flows in the bipartite graph induced by the observation pattern. Our results show that the minimax squared error for recovery of a particular entry in the matrix is proportional to the effective resistance of the corresponding edge in the graph.
  arXiv  Detail & Related papers  (2024-09-06T02:01:03Z)
• 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)
• Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient Algorithms [5.405890484609721]
  This paper considers the problem of completing a rating matrix based on sub-sampled matrix entries as well as observed social graphs and hypergraphs. We show that there exists a emphsharp threshold on the sample probability for the task of exactly completing the rating matrix. We develop a computationally efficient matrix completion algorithm that effectively exploits the observed graphs and hypergraphs.
  arXiv  Detail & Related papers  (2024-01-16T08:25:29Z)
• Isotropic Gaussian Processes on Finite Spaces of Graphs [71.26737403006778]
  We propose a principled way to define Gaussian process priors on various sets of unweighted graphs. We go further to consider sets of equivalence classes of unweighted graphs and define the appropriate versions of priors thereon. Inspired by applications in chemistry, we illustrate the proposed techniques on a real molecular property prediction task in the small data regime.
  arXiv  Detail & Related papers  (2022-11-03T10:18:17Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• 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)
• 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)
• Bayesian matrix completion with a spectral scaled Student prior: theoretical guarantee and efficient sampling [0.30458514384586394]
  A spectral scaled Student prior is exploited to favour the underlying low-rank structure of the data matrix. We show that our approach enjoys a minimax-optimal oracle inequality which guarantees that our method works well under model misspecification.
  arXiv  Detail & Related papers  (2021-04-16T16:03:43Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

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.