Paper introduces new norms for rank-constrained optimization problems.
problem Rank-constrained optimization problems in various fields.
method Introduces a family of low-rank inducing norms and regularizers.
result Other low-rank inducing norms outperform nuclear norm in matrix completion problems.
This work simplifies proximal mapping for low-rank norms.
problem Efficient computation of proximal mappings for low-rank inducing norms.
method Reduces proximal mapping to nested binary search, solving simpler problems analytically.
result Simplified computation of proximal mappings for various norms.
Proposes GTTN for discovering all low-rank structures in deep multi-task learning.
problem Discovering all low-rank structures among tasks in deep multi-task models.
method Introduces GTTN, a convex combination of matrix trace norms of all tensor flattenings, to automatically determine the importance of components.
result Demonstrates the effectiveness of GTTN on real-world datasets.
Convex norms improve coupled matrix and tensor completion.
problem Efficiently complete coupled matrices and tensors with shared information.
method Proposed convex norms and completion algorithm.
result Excess risk bounds show improved performance compared to uncoupled norms.
This work investigates implicit bias in multiclass separable data using a novel geometry-aware optimizer.
problem Understanding implicit bias in overparameterized models on multiclass separable data.
method Introduces NucGD, a geometry-aware optimizer enforcing low-rank structures through nuclear norm constraints.
result NucGD enables scalable training and characterizes the impact of stochastic optimization dynamics.
This work examines how low-rank weights improve adversarial robustness in neural networks.
problem Improving adversarial robustness in neural networks.
method The study investigates the impact of low-rank structure on adversarial robustness through compression measures.
result Promoting low-rank structure in weight matrices enhances adversarial robustness in neural networks.
Survey on nonconvex penalties for sparse and low-rank recovery in various fields.
problem Achieving sparsity and low-rankness in signal processing, statistics, and machine learning.
method Analysis of nonconvex penalties and their applications.
result Nonconvex penalties can significantly improve performance in various applications.
Dropout improves neural network performance by promoting low-rank solutions.
problem Improving neural network generalization through regularization.
method Analyzing Dropout, DropBlock, and DropConnect as regularizers for linear networks and extending to deep networks.
result Dropout, DropBlock, and DropConnect induce low-rank solutions and can be computed in closed form.
Paper solves TRPCA problem for tensor data with new tensor nuclear norm.
problem Exact recovery of tensor low-rank and sparse components.
method Introduces tensor-tensor product and new tensor nuclear norm to solve TRPCA.
result The new tensor nuclear norm guarantees exact recovery of tensor data.
Recovering a low-rank tensor from incomplete information is a recurring problem in signal processing and machine learning. The most popular convex relaxation of this problem minimizes the sum of the nuclear norms of the unfoldings of the tensor. We show that this approach can be substantially suboptimal: reliably recov…
This work proves exact low tubal rank tensor recovery from Gaussian measurements.
problem Low rank tensor recovery from Gaussian measurements.
method Careful choice of atomic set and computation of Gaussian width for atomic norm.
result Exact recovery of tensors with tubal rank r from O(r(n1+n2−r)n3) Gaussian measurements. Paper refines null space conditions for nuclear norm minimization in low-rank matrix recovery.
problem Establishing conditions for successful nuclear norm minimization recovery of low-rank matrices.
method Developed new null space conditions for nuclear norm minimization, proving their necessity and sufficiency.
result Weak null space condition is sufficient but not necessary for nuclear norm minimization recovery, providing a new necessary and sufficient condition.
Regularization can induce grokking in neural networks, improving generalization.
problem Delayed generalization following overfitting in neural networks.
method Demonstrates that gradient descent with small regularization of model properties induces grokking.
result Regularization can induce grokking, extending previous work on weight decay.
New tensor recovery method improves efficiency under strict complementarity.
problem Efficiently recovering low-rank tensors using tensor nuclear norm.
method Developed strict complementarity condition for tensor nuclear norm ball and applied to gradient methods.
result Standard gradient methods achieve linear convergence and nearly linear runtime under strict complementarity.
New nonconvex regularizers improve low-rank matrix recovery efficiency and accuracy.
problem Efficiently recover low-rank matrices from incomplete data.
method Factor group-sparse regularization, related to Schatten-p norms.
result Improved generalization error bounds for Schatten-p norms as p decreases.
We consider the problem of approximately reconstructing a partially-observed, approximately low-rank matrix. This problem has received much attention lately, mostly using the trace-norm as a surrogate to the rank. Here we study low-rank matrix reconstruction using both the trace-norm, as well as the less-studied max-no…
We consider the problem of unveiling the implicit network structure of node interactions (such as user interactions in a social network), based only on high-frequency timestamps. Our inference is based on the minimization of the least-squares loss associated with a multivariate Hawkes model, penalized by ℓ1 and t…
New pivoting strategy improves trace norm contraction in low-rank approximation.
problem Finding good low-rank approximations of symmetric, positive-definite matrices.
method Choosing rows with likelihood proportional to Aii2 for randomly pivoted partial Cholesky algorithm. result Same trace norm contraction result in Frobenius norm for improved pivoting strategy.
We address some theoretical guarantees for Schatten-p quasi-norm minimization (p∈(0,1]) in recovering low-rank matrices from compressed linear measurements. Firstly, using null space properties of the measurement operator, we provide a sufficient condition for exact recovery of low-rank matrices. This condition…
The study analyzes robustness of estimators in linear models with adversarial errors.
problem Analyzing robustness of estimators in linear models with adversarial errors.
method Develops a general theory for minimum norm interpolating estimators and RERM in linear models without conditions on errors.
result Quantitative bound for the prediction error relating it to Rademacher complexity, norm of minimum norm interpolator of errors, and subdifferential size.
New nonconvex regularizer speeds up low-rank matrix completion.
problem Low-rank matrix completion with good theoretical and empirical performance.
method Proposes a new nonconvex regularizer with adaptive shrinkage, scalable, and fast optimization.
result Proposed method achieves state-of-the-art recovery performance and is the fastest.
A new algorithm estimates mean adaptively to covariance, faster and more flexible than existing methods.
problem Estimating mean of a distribution with unknown covariance efficiently and privately.
method Adaptive differentially private algorithm with optimal convergence rates and near-linear sample complexity.
result Achieves optimal rates of convergence with respect to the Mahalanobis norm ∣∣⋅∣∣Σ. Paper tackles low-rank matrix recovery with column ℓ2,0-norm regularization.
problem Low-rank matrix recovery problems with column sparsity constraints.
method Developed alternating majorization-minimization (AMM) methods with extrapolation and hybrid AMM.
result Global convergence analysis and superior performance in matrix completion problems.
Simple algorithms improve ℓp-norm low-rank approximations.
problem Efficiently approximating matrices with low rank using ℓp norms. method Non-convex gradient-based algorithms with polynomial time complexity.
result Achieves (1+ε)-OPT approximations. The paper tackles matrix estimation from noisy data, focusing on low-rank matrices.
problem Estimating a low-rank matrix from noisy observations.
method The paper analyzes several estimators, including constrained nuclear-norm minimization, nuclear-norm regularized least squares, and a nonconvex constrained low-rank optimization problem.
result The estimators provide upper error bounds that depend on matrix rank, observed fraction, and matrix sums, and are minimax optimal.
SpINNEr uses matrix regression to analyze brain connectivity, improving accuracy over other methods.
problem Analyzing multi-dimensional data like brain imaging arrays using traditional scalar regression methods.
method SpINNEr applies matrix regression with nuclear norm and lasso norms to encourage low rank and sparse solutions.
result SpINNEr outperforms other methods in estimating brain connectivity, especially in well-connected regions.
A new tensor p-shrinkage nuclear norm improves low-rank tensor completion.
problem Estimating tensors from partial observations with low rank.
method Proposed tensor p-shrinkage nuclear norm (p-TNN) and an efficient algorithm.
result Upper bound of recovery error provided for the LRTC model.
Paper improves MVSC using tensor low-rank modeling.
problem Improving multi-view spectral clustering.
method Structured tensor low-rank norm for MVSC optimization.
result Proposed method outperforms state-of-the-art methods.
New method for tensor recovery with fewer samples.
problem Recovering low-TT-rank tensors from few samples.
method Minimizing a weighted sum of nuclear norms of unfoldings.
result Significantly fewer samples required for recovery.
This work presents a general framework for solving the low rank and/or sparse matrix minimization problems, which may involve multiple non-smooth terms. The Iteratively Reweighted Least Squares (IRLS) method is a fast solver, which smooths the objective function and minimizes it by alternately updating the variables an…
Gradient descent in deep matrix factorization favors low-rank solutions, improving recovery accuracy.
problem Understanding the generalization in deep learning models.
method Study of gradient descent over deep linear neural networks for matrix completion and sensing.
result Adding depth enhances an implicit tendency towards low-rank solutions, leading to more accurate recovery.
Paper proposes a new matrix recovery method relaxing uniform sampling assumptions.
problem Matrix completion under arbitrary sampling schemes.
method Max-norm and nuclear-norm regularization, alternating direction method of multipliers.
result The proposed method achieves fast rates of convergence and is computationally efficient.
This work improves robustness guarantees for neural networks using low rank representations.
problem Certified robustness to adversarial perturbations in neural networks.
method Low rank representations to provide improved robustness guarantees.
result Improved robustness guarantees for ℓ∞ perturbations using natural low rank representations. Robust tensor ring completion improves tensor recovery accuracy and efficiency.
problem Tensor completion sensitivity to sparse components.
method Robust Tensor Ring Completion (RTRC) with weighted nuclear norms and l1 regularization.
result Exact recovery guarantees and superior performance in various tasks.
A distributed algorithm for learning low-rank matrices from large datasets.
problem Learning high-dimensional low-rank matrices from distributed data with trace norm constraint.
method DFW-Trace, a distributed Frank-Wolfe algorithm using power method approximations.
result DFW-Trace achieves sublinear convergence to optimal solutions with few power iterations.
New method reduces tensor completion sample complexity to nearly optimal levels.
problem Low rank tensor completion with noisy measurements.
method Using atomic-norm and max-quasi-norm for tensor completion.
result Optimal sample complexity of O(dN) achieved for tensor completion. Proposes new ℓ0-based methods for low-rank sparse subspace clustering.
problem Clustering high-dimensional data points represented by low-dimensional subspaces.
method Introduces two ℓ0 quasi-norm based regularizations: GMC-LRSSC and S0/ℓ0-LRSSC. Solves resulting nonconvex optimization problems using alternating direction method of multipliers. result Demonstrates effectiveness of proposed methods on synthetic and real-world datasets.
The study analyzes perturbation bounds for HOSVD and introduces new tensor denoising estimators.
problem Perturbation analysis of HOSVD under random noise.
method Developed sup-norm perturbation bounds and introduced new tensor denoising estimators.
result Sharp deviation bounds in the sup-norm for singular subspaces and fast convergence rate for tensor denoising.
The paper estimates matrix-valued functions with low rank using penalized estimators.
problem Estimating matrix-valued functions with low rank from incomplete data.
method Innovative nuclear norm penalized local polynomial estimator and bias-reducing kernels.
result Optimal rates of convergence for various matrix norms.
The problem of low-rank approximation with convex constraints, which appears in data analysis, system identification, model order reduction, low-order controller design and low-complexity modelling is considered. Given a matrix, the objective is to find a low-rank approximation that meets rank and convex constraints, w…
This paper aims at achieving a simultaneously sparse and low-rank estimator from the semidefinite population covariance matrices. We first benefit from a convex optimization which develops l1-norm penalty to encourage the sparsity and nuclear norm to favor the low-rank property. For the proposed estimator, we then p…
Algorithm leverages low-rank relations between surrogate tasks for structured prediction.
problem Structured prediction with large or infinite-dimensional surrogate spaces.
method Trace norm regularization to leverage relationships between surrogate outputs without explicit coding/decoding functions.
result Our algorithm can improve generalization performance over previous methods.
Weight Decay induces low-rank weight matrices in neural networks, improving generalization.
problem Improving generalization in neural networks.
method Training ReLU NN with Weight Decay and Stochastic Gradient Descent.
result The weight matrix of a trained NN is approximately rank-two.
For the problems of low-rank matrix completion, the efficiency of the widely-used nuclear norm technique may be challenged under many circumstances, especially when certain basis coefficients are fixed, for example, the low-rank correlation matrix completion in various fields such as the financial market and the low-ra…
Efficient solver for nonconvex tensor regularization reduces computational cost.
problem Computational inefficiency in extending nonconvex regularization to tensor learning.
method Proximal average algorithm with adaptive momentum, maintaining sparse plus low-rank structure.
result Shows good statistical performance and accuracy on tensor completion problems.
We introduce a new framework for optimal transport using Schatten-p regularization to recover low-rank structures.
problem Optimal transport problems with low-rank structure recovery.
method Schatten-p norm regularization to promote low-rank structure in transport maps and plans.
result Unified convex programs for low-rank structure recovery with theoretical guarantees and efficient algorithms.
New method for factor analysis using nuclear and ℓ0 norms.
problem Finding a low-rank plus sparse decomposition from noisy covariance matrix.
method Formulated an optimization problem with nuclear norm, ℓ0 norm, and KL divergence. Used alternating minimization algorithm. result Algorithm effectively decomposes covariance matrices in synthetic and real datasets.
Matrix completion works well for smooth non-linear structures, even without low-rank assumptions.
problem Matrix completion for smooth non-linear structures.
method Nuclear-norm penalization for matrices lying in a low-dimensional non-linear manifold.
result Nuclear-norm penalization is minimax rate optimal for recovering smooth non-linear matrices with missing data.