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.
Optimization problems with rank constraints appear in many diverse fields such as control, machine learning and image analysis. Since the rank constraint is non-convex, these problems are often approximately solved via convex relaxations. Nuclear norm regularization is the prevailing convexifying technique for dealing …
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.
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…
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…
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…
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.
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.
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.
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.
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…
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.
The higher order singular value decomposition (HOSVD) of tensors is a generalization of matrix SVD. The perturbation analysis of HOSVD under random noise is more delicate than its matrix counterpart. Recently, polynomial time algorithms have been proposed where statistically optimal estimates of the singular subspaces …
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.
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.
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…
We propose a set of convex low rank inducing norms for a coupled matrices and tensors (hereafter coupled tensors), which shares information between matrices and tensors through common modes. More specifically, we propose a mixture of the overlapped trace norm and the latent norms with the matrix trace norm, and then, 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.
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…
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.
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.
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.
Minimizing the nuclear norm of a matrix has been shown to be very efficient in reconstructing a low-rank sampled matrix. Furthermore, minimizing the sum of nuclear norms of matricizations of a tensor has been shown to be very efficient in recovering a low-Tucker-rank sampled tensor. In this paper, we propose to recover…
Advances robust principal component analysis with transformed ℓ1 regularization.
problem Recovering low-rank structures from noisy, partially observed data corrupted by sparse outliers.
method Proposes transformed ℓ1 (TL1) regularization to improve approximations of rank and ℓ0 functional.
result Achieves higher accuracy in estimating low-rank and sparse components compared to classical convex models, especially under non-uniform sampling schemes.
Recovering a large matrix from limited measurements is a challenging task arising in many real applications, such as image inpainting, compressive sensing and medical imaging, and this kind of problems are mostly formulated as low-rank matrix approximation problems. Due to the rank operator being non-convex and discont…
New model reduces matrix factorization bias, yielding truly low-rank solutions.
problem Gradient descent's implicit bias in matrix factorization.
method Introducing a new factorization model with constrained factors and diagonal components.
result The new model consistently exhibits a strong implicit bias, yielding truly low-rank solutions.
Proposes tensor Q-rank for better tensor rank recovery in complex data.
problem Improving tensor rank recovery for complex data with low sampling rate.
method Introduces tensor Q-rank and two selection methods for Q, proposing VMTQN and MOTQN models. result Demonstrates superior performance in tensor completion problems compared to TNN-based methods.
In the past decade, sparse and low-rank recovery have drawn much attention in many areas such as signal/image processing, statistics, bioinformatics and machine learning. To achieve sparsity and/or low-rankness inducing, the ℓ1 norm and nuclear norm are of the most popular regularization penalties due to their co…
We analyze low rank tensor completion (TC) using noisy measurements of a subset of the tensor. Assuming a rank-r, order-d, N×N×⋯×N tensor where r=O(1), the best sampling complexity that was achieved is O(N2d), which is obtained by solving a tensor nuclear-norm minimizatio…
This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-unif…
Develops TOFU for tensor bandits with low-rank structure.
problem Linear bandit models fail to capture high-dimensional, low-rank tensor structures.
method Develops TOFU, a tensor bandit algorithm that estimates low-dimensional subspaces and uses norm constraints.
result Improves regret bound by a multiplicative factor that grows exponentially in system order.
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…
Sign-RIP improves robust low-rank matrix recovery by preserving norms even with corrupted measurements.
problem Robust low-rank matrix recovery in the presence of corrupted measurements.
method Proposed Sign-RIP, a robust restricted isometry property.
result Sign-RIP guarantees uniform convergence of subdifferentials in robust low-rank matrix recovery.
Unified approach for robust low rank matrix estimation with adversaries.
problem Robust low rank matrix estimation in the presence of adversaries.
method Unified approach combining Huber loss and nuclear norm penalization.
result Sharp estimation error bounds for matrix compressed sensing and completion.
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.
This paper tackles fitting multilevel low rank matrices by addressing three problems.
problem Fitting a given matrix by an MLR matrix in the Frobenius norm.
method Factor fitting, rank allocation, and hierarchical partitioning.
result The proposed methods can fit a given matrix by an MLR matrix in the Frobenius norm.
Solves low-rank approximation problems in Hilbert spaces.
problem Low-rank approximation in Hilbert spaces.
method Closed-form solutions and error bounds for bounded linear operators.
result Generalization to bounded linear operators from finite dimensions.
Mirror descent algorithm recovers low-rank matrices in matrix sensing.
problem Matrix sensing with low-rank matrices under certain conditions.
method Discrete-time mirror descent applied to empirical risk with Bregman divergence analysis.
result Mirror descent converges to a matrix minimizing a specific nuclear norm-related quantity.
We consider the problem of learning a high-dimensional but low-rank matrix from a large-scale dataset distributed over several machines, where low-rankness is enforced by a convex trace norm constraint. We propose DFW-Trace, a distributed Frank-Wolfe algorithm which leverages the low-rank structure of its updates to ac…
New algorithm improves tensor completion performance.
problem Tensor completion for partially observed data.
method Adaptive ADMM optimization framework for low-rank tensor completion.
result New method outperforms conventional techniques in NMSE.
This work solves TRPCA under linear transforms, recovering low-rank and sparse components.
problem Exact recovery of tensor low-rank and sparse components from their sum.
method Convex optimization with weighted tensor nuclear norm and ℓ1-norm.
result The convex program exactly recovers the components under certain incoherence conditions.
A new method classifies color images using quaternion algebra.
problem Classifying color images with preserved intrinsic relationships.
method LSQMM model with quaternion nuclear norm regularization and ADMM algorithm.
result LSQMM outperforms state-of-the-art methods in classification accuracy and efficiency.