Matrix Completion with Sparse Noisy Rows

• URL: http://arxiv.org/abs/2204.01530v2
• Date: Tue, 5 Apr 2022 02:05:19 GMT
• Title: Matrix Completion with Sparse Noisy Rows
• Authors: Jafar Jafarov
• Abstract summary: We study exact low-rank completion under non-degenerate noise model. In this paper, we assume that each row can receive random noise instead of columns.
• Score: 3.42658286826597
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Exact matrix completion and low rank matrix estimation problems has been studied in different underlying conditions. In this work we study exact low-rank completion under non-degenerate noise model. Non-degenerate random noise model has been previously studied by many researchers under given condition that the noise is sparse and existing in some of the columns. In this paper, we assume that each row can receive random noise instead of columns and propose an interactive algorithm that is robust to this noise. We show that we use a parametrization technique to give a condition when the underlying matrix could be recoverable and suggest an algorithm which recovers the underlying matrix.

Related papers

• Information limits and Thouless-Anderson-Palmer equations for spiked matrix models with structured noise [19.496063739638924]
  We consider a saturate problem of Bayesian inference for a structured spiked model. We show how to predict the statistical limits using an efficient algorithm inspired by the theory of adaptive Thouless-Anderson-Palmer equations.
  arXiv  Detail & Related papers  (2024-05-31T16:38:35Z)
• Optimality of Approximate Message Passing Algorithms for Spiked Matrix Models with Rotationally Invariant Noise [12.64438771302935]
  We study the problem of estimating a rank one signal matrix from an observed matrix generated by corrupting the signal with additive rotationally invariant noise. We develop a new class of approximate message-passing algorithms for this problem and provide a simple and concise characterization of their dynamics in the high-dimensional limit.
  arXiv  Detail & Related papers  (2024-05-28T11:42:51Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  We study matrix estimation problems arising in reinforcement learning (RL) with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it may for example characterize the transition kernel of the MDP. We show that simple spectral-based matrix estimation approaches efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise error.
  arXiv  Detail & Related papers  (2023-10-10T17:06:41Z)
• Adaptive Noisy Matrix Completion [0.0]
  We assume that the matrix $mathbfM$ we target to recover is composed as low-rank matrix with addition of bounded small noise. We study this problem in adaptive setting that, we continuously estimate an upper bound for the angle with the underlying low-rank subspace and noise-added subspace.
  arXiv  Detail & Related papers  (2022-03-16T01:20:18Z)
• Implicit Regularization of Sub-Gradient Method in Robust Matrix Recovery: Don't be Afraid of Outliers [6.320141734801679]
  We show that a simple sub-gradient method converges to the true low-rank solution efficiently. We also build upon a new notion of restricted isometry property, called sign-RIP, to prove the robustness of the method.
  arXiv  Detail & Related papers  (2021-02-05T02:52:00Z)
• Learning Noise Transition Matrix from Only Noisy Labels via Total Variation Regularization [88.91872713134342]
  We propose a theoretically grounded method that can estimate the noise transition matrix and learn a classifier simultaneously. We show the effectiveness of the proposed method through experiments on benchmark and real-world datasets.
  arXiv  Detail & Related papers  (2021-02-04T05:09:18Z)
• Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion [17.615174152419133]
  It is not known which revealed entries are corrupted. We show that our proposed algorithm is optimal when the set of revealed entries is given by an ErdHos-R'enyi random graph. In particular, we show that our proposed algorithm is optimal when the set of revealed entries is given by an ErdHos-R'enyi random graph.
  arXiv  Detail & Related papers  (2020-10-23T06:23:20Z)
• Learning Mixtures of Low-Rank Models [89.39877968115833]
  We study the problem of learning computational mixtures of low-rank models. We develop an algorithm that is guaranteed to recover the unknown matrices with near-optimal sample. In addition, the proposed algorithm is provably stable against random noise.
  arXiv  Detail & Related papers  (2020-09-23T17:53:48Z)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  Robust low-rank matrix completion (RMC) has been studied extensively for computer vision, signal processing and machine learning applications. This problem aims to decompose a partially observed matrix into the superposition of a low-rank matrix and a sparse matrix, where the sparse matrix captures the grossly corrupted entries of the matrix. A widely used approach to tackle RMC is to consider a convex formulation, which minimizes the nuclear norm of the low-rank matrix (to promote low-rankness) and the l1 norm of the sparse matrix (to promote sparsity). In this paper, motivated by some recent works on low-
  arXiv  Detail & Related papers  (2020-08-18T04:46:22Z)
• 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)
• Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles [65.9694455739978]
  We study contextual linear bandit problems under feature uncertainty, where the features are noisy and have missing entries. Our analysis reveals that the optimal hypothesis can significantly deviate from the underlying realizability function, depending on the noise characteristics. This implies that classical approaches cannot guarantee a non-trivial regret bound.
  arXiv  Detail & Related papers  (2017-03-03T21:39: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.