We give the first algorithm for Matrix Completion whose running time and sample complexity is polynomial in the rank of the unknown target matrix, linear in the dimension of the matrix, and logarithmic in the condition number of the matrix. To the best of our knowledge, all previous algorithms either incurred a quadrat…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,738 papers · 148 categories
Trend · papers per month
48 results for “matrix conditions”
Implicit Regularization in Perturbed Deep Matrix Factorization: Spectral Conditions and Stabilitymath.OC
The paper examines how gradient descent stabilizes low-rank matrix factorization in noisy conditions.
problem Stability of low-rank implicit regularization in perturbed deep matrix factorization.
method Derives spectral conditions for gradient descent to exhibit a low-rank phase in noiseless settings and analyzes perturbed dynamics.
result Gradient descent converges to a low-rank solution under perturbation, with explicit dependence on perturbation size.
Low-rank matrix recovery has found many applications in science and engineering such as machine learning, signal processing, collaborative filtering, system identification, and Euclidean embedding. But the low-rank matrix recovery problem is an NP hard problem and thus challenging. A commonly used heuristic approach is…
ScaledGD improves gradient descent for ill-conditioned low-rank matrix estimation.
problem Efficiently solving ill-conditioned low-rank matrix estimation problems.
method Scaled Gradient Descent (ScaledGD) with adaptive pre-conditioners.
result Linear convergence rate independent of condition number, low per-iteration cost.
To estimate the conditional probability functions based on the direct problem setting, V-matrix based method was proposed. We construct V-matrix based constrained quadratic programming problems for which the inequality constraints are inconsistent. In particular, we would like to present that the constrained quadratic …
Improved perturbation reduces matrix condition number to O(n) with minimal storage.
problem Reducing the condition number of deterministic matrices for efficient algorithmic use.
method Introduced pattern matrices and sparse perturbations with dependent entries.
result Condition number reduced to O(n) with O(n) random numbers in O(log n) precision.
In this paper, we review the problem of matrix completion and expose its intimate relations with algebraic geometry, combinatorics and graph theory. We present the first necessary and sufficient combinatorial conditions for matrices of arbitrary rank to be identifiable from a set of matrix entries, yielding theoretical…
Proposes a new method for selecting regularization parameters in sparse precision matrix estimation.
problem Selecting an appropriate regularization parameter for sparse precision matrix estimation.
method Developed a closed-form matrix-valued regularization parameter based on the sampling distribution of optimality conditions.
result The proposed method achieves comparable estimation accuracy and superior support recovery to cross-validation, with significant runtime improvements.
Improved convergence for overparameterized low-rank matrix sensing.
problem Overparameterized low-rank matrix sensing with unknown rank and ill-conditioning.
method ScaledGD() - preconditioned gradient descent method.
result ScaledGD() converges at a constant linear rate after a logarithmic number of iterations.
Link signature limit depends on linking matrix under specific polynomial condition.
problem Limits of Tristam-Levine signature function under precise polynomial conditions.
method Analysis of Alexander polynomial and linking matrix.
result Limit of Tristam-Levine signature at 1 determined by linking matrix under specific polynomial condition.
This paper considers inference over distributed linear Gaussian models using factor graphs and Gaussian belief propagation (BP). The distributed inference algorithm involves only local computation of the information matrix and of the mean vector, and message passing between neighbors. Under broad conditions, it is show…
The study characterizes the conditioning of the Gauss-Newton matrix in neural networks.
problem Understanding the conditioning of the Gauss-Newton matrix in neural networks.
method Theoretical analysis of the GN matrix in deep linear and ReLU networks, extending to residual connections and convolutional layers.
result Established tight bounds on the condition number of the GN matrix in neural networks.
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…
This paper considers the matrix completion problem. We show that it is not necessary to assume joint incoherence, which is a standard but unintuitive and restrictive condition that is imposed by previous studies. This leads to a sample complexity bound that is order-wise optimal with respect to the incoherence paramete…
Preconditioned SGD accelerates convergence for ill-conditioned huge-scale matrix completion.
problem Recovering a low-rank matrix from incomplete data with high condition number.
method Preconditioned Stochastic Gradient Descent (SGD) for huge-scale online optimization.
result Preconditioned SGD converges to ε-accuracy in O(log(1/ε)) iterations, compared to O(κlog(1/ε)) for unpreconditioned SGD.
High-dimensional settings, where the data dimension () far exceeds the number of observations (), are common in many statistical and machine learning applications. Methods based on -relaxation, such as Lasso, are very popular for sparse recovery in these settings. Restricted Eigenvalue (RE) condition is a…
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.
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 proposes fast, robust methods for low-rank matrix recovery.
problem Estimating low-rank matrices from incomplete or corrupted data.
method Scaled subgradient methods for nonsmooth, nonconvex formulations.
result Methods converge almost dimension-free and condition-number independent.
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.
We consider the matrix completion problem with a deterministic pattern of observed entries. In this setting, we aim to answer the question: under what condition there will be (at least locally) unique solution to the matrix completion problem, i.e., the underlying true matrix is identifiable. We answer the question fro…
Paper proves min-vol NMF robust to noise under expanded condition.
problem Robustness of min-vol NMF to noise.
method Proved robustness under expanded sufficiently scattered condition.
result Proves min-vol NMF identifies groundtruth factors in noise.
An analysis is made of reality conditions within the context of noncommutative geometry. We show that if a covariant derivative satisfies a given left Leibniz rule then a right Leibniz rule is equivalent to the reality condition. We show also that the matrix which determines the reality condition must satisfy the Yang-…
The paper addresses ill-conditioning in large spatial data, proposing solutions for prediction and likelihood estimation.
problem Ill-conditioning of the kernel matrix in large spatial data sets.
method Introduction of various optimality criteria and solutions for managing large spatial data.
result Solutions for managing large spatial data, addressing ill-conditioning and improving prediction and likelihood estimation.
Projection-cost preservation is a low-rank approximation guarantee which ensures that the cost of any rank- projection can be preserved using a smaller sketch of the original data matrix. We present a general structural result outlining four sufficient conditions to achieve projection-cost preservation. These condit…
We show some properties of a Seifert matrix of an -component Brunnian link. In particular, we give a necessary and sufficient condition for a matrix to be a Seifert matrix of a 2-component Brunnian link up to S-equivalence.
HSNLD solves robust Hankel recovery efficiently and robustly.
problem Robust Hankel recovery of sparse outliers and missing entries.
method Hankel Structured Newton-Like Descent (HSNLD) algorithm.
result HSNLD achieves linear convergence independent of the condition number.
In this article we give an explicit description of the representation matrix of a Heisenberg type action constructed by Blanchet, Habegger, Masbaum and Vogel. We give the matrix in terms of a ribbon graph and its admissible colorings. We show that components of the representation matrix satisfies the {\it external edge…
AMP algorithm for matrix tensor product model provides recovery conditions.
problem Generalization of standard spiked matrix models with multiple pairwise observations.
method Approximate message passing with optimal weighing and combining of estimates.
result Asymptotically exact performance description and necessary/sufficient recovery conditions.
The paper analyzes stability of random matrix products with Markovian noise.
problem Analyzing stability of random matrix products with Markovian noise.
method Using a super-Lyapunov drift condition and controlled growth of matrix-valued functions, the paper provides an exponential stability result for the p-th moment of random matrix product.
result Finite-time p-th moment bounds for linear stochastic approximation and TD learning algorithms.
The stability and robustness of compact schemes for parabolic PDEs are analyzed.
problem Stability and robustness of compact schemes for solving parabolic PDEs.
method Compact spatial discretization, Crank-Nicolson temporal discretization, eigenvalue analysis of amplification matrix.
result An upper bound on the condition number of the amplification matrix is derived, showing stability.
Given i.i.d. observations of a random vector , where is a high-dimensional vector and is a low-dimensional index variable, we study the problem of estimating the conditional inverse covariance matrix under the assumption that the set of non…
Low-rank matrix completion (LRMC) problems arise in a wide variety of applications. Previous theory mainly provides conditions for completion under missing-at-random samplings. This paper studies deterministic conditions for completion. An incomplete matrix is finitely rank- completable if there are at …
The Gaussian graphical model, a popular paradigm for studying relationship among variables in a wide range of applications, has attracted great attention in recent years. This paper considers a fundamental question: When is it possible to estimate low-dimensional parameters at parametric square-root rate in a large Gau…
Recently, Neural networks have seen a huge surge in its adoption due to their ability to provide high accuracy on various tasks. On the other hand, the existence of adversarial examples have raised suspicions regarding the generalization capabilities of neural networks. In this work, we focus on the weight matrix learn…
Improved covariance matrix estimation for portfolio optimization with guaranteed PSD and controlled conditioning.
problem Guaranteeing positive semidefinite ness and controlling spectral conditioning in IQ estimators.
method Introducing squeezing identity and atomic-IQ parameterization to construct structured channel matrices with PSD guarantees and analytic eigen floor for conditioning control.
result Atomic-IQ improves Sharpe ratios and delivers a more stable risk profile compared to standard estimators.
Optimization problems with rank constraints arise in many applications, including matrix regression, structured PCA, matrix completion and matrix decomposition problems. An attractive heuristic for solving such problems is to factorize the low-rank matrix, and to run projected gradient descent on the nonconvex factoriz…
New method infers graph from dependent matrix data.
problem Inferring graph from dependent matrix data.
method Sparse-group lasso-based frequency-domain formulation with ADMM approach.
result Local convergence of inverse PSD estimators to true value.
New methods estimate covariance for matrix data without assuming fixed size or specific distributions.
problem Estimating covariance for high-dimensional matrix data without distributional assumptions.
method Unified framework for bandable covariance estimation with rank one approximation, robust to heavy-tailed data.
result Proposed estimators are rate-optimal and perform well in simulations and real applications.
Scalable method completes ill-conditioned matrices from few samples.
problem Matrix completion from few samples for ill-conditioned matrices.
method Iterative algorithm combining IRLS, smoothing Newton, and proximal gradient methods.
result Local quadratic convergence rate and well-conditioned linear systems.
Given a real matrix A with n columns, the problem is to approximate the Gram product AA^T by c << n weighted outer products of columns of A. Necessary and sufficient conditions for the exact computation of AA^T (in exact arithmetic) from c >= rank(A) columns depend on the right singular vector matrix of A. For a Monte-…
Multivariate regression model is a natural generalization of the classical univari- ate regression model for fitting multiple responses. In this paper, we propose a high- dimensional multivariate conditional regression model for constructing sparse estimates of the multivariate regression coefficient matrix that accoun…
SGD with mini-batches can solve convex low-rank matrix problems efficiently.
problem Solving large-scale convex low-rank matrix problems efficiently.
method Stochastic Gradient Descent with mini-batches and low-rank projections.
result SGD with mini-batches produces low-rank iterates with high probability.
Proposes a new matrix factorization model for interval-valued matrices.
problem Matrix factorization for matrices with entries in a given interval.
method Bounded simplex-structured matrix factorization (BSSMF) with fast algorithm for missing data.
result BSSMF provides a unique decomposition under certain conditions.
We consider the problem of covariance matrix estimation in the presence of latent variables. Under suitable conditions, it is possible to learn the marginal covariance matrix of the observed variables via a tractable convex program, where the concentration matrix of the observed variables is decomposed into a sparse ma…
Fast estimation of Kendall's Tau and conditional Kendall's Tau matrices under structural assumptionsmath.ST
New estimators reduce computation for Kendall's tau and conditional Kendall's tau matrices under structural assumptions.
problem Efficient estimation of Kendall's tau and conditional Kendall's tau matrices for large dimensions.
method Averaging pairwise estimates over blocks or conditional estimates, exploiting structural assumptions.
result Improved estimators with reduced computational cost and similar error level.
Paper proposes a clustering algorithm for nonnegative data.
problem Clustering nonnegative data in disjoint subspaces.
method Simple algorithm to cluster nonnegative data.
result Matrix completion algorithm outperforms standard methods.
We address the rectangular matrix completion problem by lifting the unknown matrix to a positive semidefinite matrix in higher dimension, and optimizing a nonconvex objective over the semidefinite factor using a simple gradient descent scheme. With random observations of a $n_1 \times n…