On the phase diagram of extensive-rank symmetric matrix denoising beyond rotational invariance

• URL: http://arxiv.org/abs/2411.01974v1
• Date: Mon, 04 Nov 2024 10:50:37 GMT
• Title: On the phase diagram of extensive-rank symmetric matrix denoising beyond rotational invariance
• Authors: Jean Barbier, Francesco Camilli, Justin Ko, Koki Okajima,
• Abstract summary: We make progress towards the understanding of matrix denoising when the hidden signal is a factored matrix $XXintercal$ that is not rotationally invariant. We argue that it is only beyond the transition that factorisation, i.e., estimating $X$ itself, becomes possible up to sign and permutation universality. We also argue that it is only beyond the transition that factorisation, i.e., estimating $X$ itself, becomes possible up to sign and permutation universality.
• Score: 5.058205542605482
• License:
• Abstract: Matrix denoising is central to signal processing and machine learning. Its analysis when the matrix to infer has a factorised structure with a rank growing proportionally to its dimension remains a challenge, except when it is rotationally invariant. In this case the information theoretic limits and a Bayes-optimal denoising algorithm, called rotational invariant estimator [1,2], are known. Beyond this setting few results can be found. The reason is that the model is not a usual spin system because of the growing rank dimension, nor a matrix model due to the lack of rotation symmetry, but rather a hybrid between the two. In this paper we make progress towards the understanding of Bayesian matrix denoising when the hidden signal is a factored matrix $XX^\intercal$ that is not rotationally invariant. Monte Carlo simulations suggest the existence of a denoising-factorisation transition separating a phase where denoising using the rotational invariant estimator remains Bayes-optimal due to universality properties of the same nature as in random matrix theory, from one where universality breaks down and better denoising is possible by exploiting the signal's prior and factorised structure, though algorithmically hard. We also argue that it is only beyond the transition that factorisation, i.e., estimating $X$ itself, becomes possible up to sign and permutation ambiguities. On the theoretical side, we combine mean-field techniques in an interpretable multiscale fashion in order to access the minimum mean-square error and mutual information. Interestingly, our alternative method yields equations which can be reproduced using the replica approach of [3]. Using numerical insights, we then delimit the portion of the phase diagram where this mean-field theory is reliable, and correct it using universality when it is not. Our ansatz matches well the numerics when accounting for finite size effects.

Related papers

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Learning Large Causal Structures from Inverse Covariance Matrix via Sparse Matrix Decomposition [2.403264213118039]
  This paper focuses on learning causal structures from the inverse covariance matrix. The proposed method, called ICID, is based on continuous optimization of a matrix decomposition model. We show that ICID efficiently identifies the sought directed acyclic graph (DAG) assuming the knowledge of noise variances.
  arXiv  Detail & Related papers  (2022-11-25T16:32:56Z)
• Orthogonal Matrix Retrieval with Spatial Consensus for 3D Unknown-View Tomography [58.60249163402822]
  Unknown-view tomography (UVT) reconstructs a 3D density map from its 2D projections at unknown, random orientations. The proposed OMR is more robust and performs significantly better than the previous state-of-the-art OMR approach.
  arXiv  Detail & Related papers  (2022-07-06T21:40:59Z)
• 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)
• Statistical limits of dictionary learning: random matrix theory and the spectral replica method [28.54289139061295]
  We consider increasingly complex models of matrix denoising and dictionary learning in the Bayes-optimal setting. We introduce a novel combination of the replica method from statistical mechanics together with random matrix theory, coined spectral replica method.
  arXiv  Detail & Related papers  (2021-09-14T12:02:32Z)
• Convolutional Filtering and Neural Networks with Non Commutative Algebras [153.20329791008095]
  We study the generalization of non commutative convolutional neural networks. We show that non commutative convolutional architectures can be stable to deformations on the space of operators.
  arXiv  Detail & Related papers  (2021-08-23T04:22:58Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization [36.182992409810446]
  This paper investigates the importance of noise in non optimization problems. We show that gradient descent can converge to any global form that converges to a global bias that is determined by the injected noise.
  arXiv  Detail & Related papers  (2021-02-24T17:50:17Z)
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing [36.96922859748537]
  Low-rank matrix estimation plays a central role in various applications across science and engineering. Existing approaches rely on adding a metric regularization term to balance the scale of the two matrix factors. In this paper, we provide a theoretical justification for the performance in recovering a low-rank matrix from a small number of linear measurements.
  arXiv  Detail & Related papers  (2021-01-13T15:03:52Z)
• 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)
• Convergence to Second-Order Stationarity for Non-negative Matrix Factorization: Provably and Concurrently [18.89597524771988]
  Non-negative matrix factorization (NMF) is a fundamental non-modification optimization problem with numerous applications in Machine Learning. This paper defines a multiplicative weight update type dynamics (Seung algorithm) that runs concurrently and provably avoids saddle points. An important advantage is the use concurrent implementations in parallel computing environments.
  arXiv  Detail & Related papers  (2020-02-26T06:40:23Z)

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.