New method solves matrix completion problems to certifiable optimality.
problem Certifying optimality in low-rank matrix completion.
method Disjunctive branch-and-bound scheme for convex relaxation.
result Decreases optimality gap by two orders of magnitude.
Dantzig Selector (DS) is widely used in compressed sensing and sparse learning for feature selection and sparse signal recovery. Since the DS formulation is essentially a linear programming optimization, many existing linear programming solvers can be simply applied for scaling up. The DS formulation can be explained a…
Researchers developed a new Riemannian manifold for SPD matrix-valued optimal transport problems.
problem Optimal transport between SPD matrix-valued measures.
method Formulated as a generalized optimal transport problem with block SPD matrices, endowed with a novel Riemannian manifold structure.
result The novel Riemannian manifold allows solving SPD matrix-valued optimal transport problems using Riemannian optimization.
New approach to convex hulls for low-rank problems.
problem Characterizing convex hulls for low-rank sets.
method Matrix perspective function and orthogonal projection matrices.
result Strong relaxations for various low-rank problems.
This work studies the strong duality of non-convex matrix factorization problems: we show that under certain dual conditions, these problems and its dual have the same optimum. This has been well understood for convex optimization, but little was known for non-convex problems. We propose a novel analytical framework an…
Paper proposes algorithms for BMF using integer programming.
problem Approximating binary input matrix as product of two smaller binary factors.
method Alternating optimization strategy using integer programming to solve subproblems and combine solutions.
result Proposed algorithms outperform state of the art on medium-scale problems.
The truncated singular value decomposition (SVD) of the measurement matrix is the optimal solution to the_representation_ problem of how to best approximate a noisy measurement matrix using a low-rank matrix. Here, we consider the (unobservable)_denoising_ problem of how to best approximate a low-rank signal matrix bur…
Unified framework for nonconvex matrix completion with linearly parameterized factors.
problem Matrix completion with improved accuracy using linearly parameterized factors.
method Unified nonconvex optimization framework with Correlated Parametric Factorization condition.
result Uniform upper bounds for low-rank estimation at any local minimum.
Unified optimization framework for matrix seriation.
problem Discovering latent structure in relational data.
method Mathematical optimization models for seriation.
result Optimization models enhance solution quality and interpretability.
Optimizing the acquisition matrix is useful for compressed sensing of signals that are sparse in overcomplete dictionaries, because the acquisition matrix can be adapted to the particular correlations of the dictionary atoms. In this paper a novel formulation of the optimization problem is proposed, in the form of a ra…
In this paper we develop a new framework that captures the common landscape underlying the common non-convex low-rank matrix problems including matrix sensing, matrix completion and robust PCA. In particular, we show for all above problems (including asymmetric cases): 1) all local minima are also globally optimal; 2) …
New method efficiently learns positive-definite curvature for neural nets.
problem Efficiently learn positive-definite curvature for neural net training.
method Spectral-factorized positive-definite curvature learning approach.
result Efficiently applies arbitrary matrix roots and generic curvature learning.
Paper proposes a new approach to optimal transport for vector and matrix densities.
problem Optimal transport for vector and matrix densities with positivity and action transitivity constraints.
method Gauge-theoretic approach using semi-direct product groups of diffeomorphisms and gauge transformations.
result Bures-type metrics on semi-direct product groups relate to Wasserstein-type metrics on vector and matrix densities via Riemannian submersions.
PolarGrad optimizes deep learning models by considering matrix structure, outperforming Adam and Muon.
problem Efficient optimization of large-scale neural networks and language models.
method A unifying framework for analyzing matrix-aware preconditioned methods, including PolarGrad.
result PolarGrad outperforms Adam and Muon in various tasks.
New algorithm improves game learning with randomised optimism.
problem Learning in matrix games with unknown payoffs and bandit feedback.
method Integrates evolutionary algorithms into bandit framework for randomised optimism.
result Achieves sublinear regret, outperforming classical methods.
We relax indicator matrices to form a manifold for faster optimization.
problem Optimizing indicator matrices is NP-hard.
method Developed a Riemannian manifold (RIM) and Riemannian optimization methods.
result RIM manifold optimization is significantly faster and yields better results.
New method improves robust low-rank matrix completion for computer vision.
problem Robust low-rank matrix completion for partially observed data.
method Formulated as a nonsmooth Riemannian optimization problem over Grassmann manifold, solved with an alternating manifold proximal gradient continuation method.
result Demonstrated advantages over existing approaches in background extraction from surveillance videos.
New algorithm optimizes matrix reordering for noisy disordered matrices.
problem Optimizing matrix reordering for noisy disordered matrices in single-cell biology and metagenomics.
method Proposed a polynomial-time adaptive sorting algorithm to improve upon spectral seriation.
result Our algorithm achieves superior performance compared to existing methods in real datasets.
A new method for 1-bit matrix completion that is faster and more accurate.
problem Estimating a low-rank matrix from binary observations.
method Majorization-Minimization Gauss-Newton (MMGN) method.
result MMGN outperforms existing methods in accuracy and speed.
We propose a unified framework for estimating low-rank matrices through nonconvex optimization based on gradient descent algorithm. Our framework is quite general and can be applied to both noisy and noiseless observations. In the general case with noisy observations, we show that our algorithm is guaranteed to linearl…
New methods improve online matrix optimization with reduced computational cost.
problem Online matrix optimization with operator norm constraints.
method Gradient-based prediction scheme with smoothed potentials for nuclear norm.
result Adaptive matrix optimizers match Shampoo's regret up to a constant factor.
New methods for sketching non-PSD matrices improve regression and optimization tasks.
problem Efficiently handling non-PSD matrices in computations.
method Developed novel matrix sketching techniques for non-PSD and complex matrices.
result Improved performance in convex and non-convex optimization, regression, and vector-matrix-vector queries.
In this work we construct an optimal shrinkage estimator for the precision matrix in high dimensions. We consider the general asymptotics when the number of variables p→∞ and the sample size n→∞ so that p/n→c∈(0,+∞). The precision matrix is estimated directly, wit…
Efficiently solves large portfolio optimization problems by reducing and sparsifying covariance matrices.
problem Large and dense covariance matrices limit efficient portfolio optimization.
method Dimension reduction and increased sparsity based on machine learning predictions.
result Improved portfolio performance and reduced runtime compared to full dense covariance matrices.
Muon optimizer simplifies matrix optimization with spectral orthogonalization.
problem Matrix optimization challenges, especially with large condition numbers.
method Simplified Muon optimizer using spectral orthogonalization of gradients.
result Simplified Muon converges linearly with independent scalar sequences, outperforming gradient descent and Adam.
Study finds weak solutions for complex map flows with optimal lifespan.
problem Existence of weak solutions for two-phase matrix-valued harmonic map flows.
method Modified minimizing movement scheme, discretizing time and interpolating solutions.
result Existence of weak solutions with optimal lifespan for the limiting system.
Teaches matrix calculus for machine learning and optimization.
problem Computing derivatives of functions involving matrices.
method Extends differential calculus to vector spaces, focusing on practical applications in machine learning.
result Introduction of adjoint and reverse-mode differentiation for efficient computation.
In this work we construct an optimal linear shrinkage estimator for the covariance matrix in high dimensions. The recent results from the random matrix theory allow us to find the asymptotic deterministic equivalents of the optimal shrinkage intensities and estimate them consistently. The developed distribution-free es…
We consider the problem of matrix completion on an n×m matrix. We introduce the problem of Interpretable Matrix Completion that aims to provide meaningful insights for the low-rank matrix using side information. We show that the problem can be reformulated as a binary convex optimization problem. We design Opt…
Paper shows no spurious local minima in a specific matrix factorization problem.
problem Optimization of ℓ1-norm rank-one symmetric matrix factorization. method Second-order variational analysis to study the landscape of the problem.
result Any second-order stationary point is globally optimal.
Scaled gradient descent improves matrix recovery for ill-conditioned matrices with optimal sampling complexity.
problem Recovering low-rank matrices from limited measurements efficiently and accurately.
method Scaled gradient descent (ScaledGD) with optimal sample complexity and improved iteration complexity.
result ScaledGD achieves optimal sample complexity and improved iteration complexity for ill-conditioned matrices.
Paper develops a decoder for sparse codes without encoder matrix, achieving optimal recovery.
problem Designing a decoder for sparse codes from linear measurements alone.
method Matrix factorization to recover encoder and sparse coding matrices from measurements.
result Decoder-Expander Based Factorisation recovers encoder and sparse coding matrix at optimal measurement rate with high probability.
Study shows generative priors improve rank-one matrix recovery with optimal sample complexity.
problem Recovering a rank-one signal matrix from noisy data with additional prior information.
method Analysis of a nonlinear least squares objective with a favorable global optimization landscape.
result Established optimal sample complexity for generative priors in rank-one matrix recovery.
Paper checks SSC for matrix factorizations using Gurobi.
problem Checking the SSC for various matrix factorizations.
method Formulated as a non-convex quadratic optimization problem over a bounded set, solved with Gurobi.
result SSC can be checked in reasonable time for realistic scenarios.
Paper proposes a matrix optimization model for reliable Euclidean embedding from noisy data.
problem Challenges in Euclidean embedding from noisy observations containing outliers.
method Matrix optimization based embedding model to detect and remove outliers.
result The model provides high accuracy estimators and successfully identifies outliers.
Equivalent formulations for low-rank matrix optimization are proven.
problem Low-rank matrix optimization with rank constraints.
method Established geometric landscape connections between manifold and factorization formulations.
result Equivalence between manifold and factorization formulations at FOSPs, SOSPs, and strict saddles.
A matrix network is a family of matrices, with relatedness modeled by a weighted graph. We consider the task of completing a partially observed matrix network. We assume a novel sampling scheme where a fraction of matrices might be completely unobserved. How can we recover the entire matrix network from incomplete obse…
A new multi-view clustering method using deep matrix decomposition and partition alignment.
problem Improving multi-view clustering methods to better utilize data representations and view-specific structures.
method Deep matrix decomposition for partition representations, joint use of partition representations, and alternating optimization.
result Demonstrated effectiveness on six benchmark datasets compared to state-of-the-art methods.
Study exact limits of matrix reconstruction from noisy projections.
problem Reconstructing matrices from linear projections with high-dimensional data.
method Asymptotic analysis, universality properties, and generalized linear models.
result Exact asymptotic equations for optimal learning performance.
Substantial progress has been made recently on developing provably accurate and efficient algorithms for low-rank matrix factorization via nonconvex optimization. While conventional wisdom often takes a dim view of nonconvex optimization algorithms due to their susceptibility to spurious local minima, simple iterative …
We study the convergence of a variant of distributed gradient descent (DGD) on a distributed low-rank matrix approximation problem wherein some optimization variables are used for consensus (as in classical DGD) and some optimization variables appear only locally at a single node in the network. We term the resulting a…
Enhances clustering performance with a novel high-order Laplacian matrix.
problem Limited representation capability and insufficient information exploitation in multi-view spectral clustering.
method Proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix.
result Improves clustering performance through enhanced representation capacity of the learned optimal Laplacian matrix.
Optimal data splitting improves covariance matrix estimation in large datasets.
problem Improving large covariance matrix estimation in high-dimensional settings.
method Focus on holdout method, derive closed-form error expression, connect to eigenvalue variance.
result Optimal train-test split scales as square root of matrix dimension.
Efficiently computes matrix square roots and their inverses for large matrices.
problem Computing matrix square roots and inverses for large matrices efficiently.
method Combines Krylov subspace methods with rational approximation for quadratic-time computation.
result Achieves 4 decimal places of accuracy with fewer than 100 matrix-vector multiplications.
This paper introduces a new data-driven methodology for estimating sparse covariance matrices of the random coefficients in logit mixture models. Researchers typically specify covariance matrices in logit mixture models under one of two extreme assumptions: either an unrestricted full covariance matrix (allowing correl…
This paper concerns a fundamental class of convex matrix optimization problems. It presents the first algorithm that uses optimal storage and provably computes a low-rank approximation of a solution. In particular, when all solutions have low rank, the algorithm converges to a solution. This algorithm, SketchyCGM, modi…
We consider the problem of estimating a low-rank matrix from a noisy observed matrix. Previous work has shown that the optimal method depends crucially on the choice of loss function. In this paper, we use a family of weighted loss functions, which arise naturally for problems such as submatrix denoising, denoising wit…
LoCoV reduces portfolio optimization errors from sample covariance matrices.
problem Large errors in sample covariance matrix for optimal portfolio weights.
method LoCoV (low dimension covariance voting) algorithm to reduce these errors.
result LoCoV outperforms classical methods in portfolio optimization experiments.