arXiv research

Analytic proof for minimal rank Sard conjecture.

Geometrically, tensors of fixed rank form a minimal submanifold.

IRMAE learns compact latent spaces by minimizing rank.

Rank minimization has attracted a lot of attention due to its robustness in data recovery. To overcome the computational difficulty, rank is often replaced with nuclear norm. For several rank minimization problems, such a replacement has been theoretically proven to be valid, i.e., the solution to nuclear norm minimiza…

Minimal submanifolds in matrix spaces proven for specific ranks.

We prove the $C^{1}$ regularity for a class of abnormal length-minimizers in rank $2$ sub-Riemannian structures. As a consequence of our result, all length-minimizers for rank $2$ sub-Riemannian structures of step up to $4$ are of class $C^{1}$.

ReLU networks implicitly favor low-rank solutions, but not as strongly as linear networks.

In this paper we consider general rank minimization problems with rank appearing in either objective function or constraint. We first establish that a class of special rank minimization problems has closed-form solutions. Using this result, we then propose penalty decomposition methods for general rank minimization pro…

Deep ResNets favor low bottleneck rank with proper hyperparameters.

We address some theoretical guarantees for Schatten-$p$ quasi-norm minimization ($p \in (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…

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…

Gradient flow with infinitesimal initialization converges to Greedy Low-Rank Learning for matrix factorization.

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…

Minimal cones defined by rank conditions in matrix spaces.

Minimizing the rank of a matrix subject to constraints is a challenging problem that arises in many applications in control theory, machine learning, and discrete geometry. This class of optimization problems, known as rank minimization, is NP-HARD, and for most practical problems there are no efficient algorithms that…

The Besson-Courtois-Gallot theorem is proven for noncompact finite volume Riemannian manifolds. In particular, no bounded geometry assumptions are made. This proves the minimal entropy conjecture for nonuniform rank one lattices.

This method infers models from data with physical insights, minimizing model order.

We obtain new curvature estimates and Bernstein type results for minimal $n-$submanifolds in $\ir{n+m},\, m\ge 2$ under the condition that the rank of its Gauss map is at most 2. In particular, this applies to minimal surfaces in Euclidean spaces of arbitrary codimension.

Multi-label classification studies the task where each example belongs to multiple labels simultaneously. As a representative method, Ranking Support Vector Machine (Rank-SVM) aims to minimize the Ranking Loss and can also mitigate the negative influence of the class-imbalance issue. However, due to its stacking-style …

We prove minimal entropy rigidity for complete, finite volume manifolds locally isometric to a product of rank one symmetric spaces of dimension at least 3: the locally symmetric metric uniquely minimizes (normalized) entropy among all Riemannian metrics. The corresponding theorem is true for maps into these spaces as …

New examples of sub-Riemannian structures satisfying Minimizing Sard conjecture found.

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…

In many applications that require matrix solutions of minimal rank, the underlying cost function is non-convex leading to an intractable, NP-hard optimization problem. Consequently, the convex nuclear norm is frequently used as a surrogate penalty term for matrix rank. The problem is that in many practical scenarios th…

In many applications that require matrix solutions of minimal rank, the underlying cost function is non-convex leading to an intractable, NP-hard optimization problem. Consequently, the convex nuclear norm is frequently used as a surrogate penalty term for matrix rank. The problem is that in many practical scenarios th…

Study on horospheres in higher rank homogeneous spaces, proving density properties.

Minimal Kaehler submanifolds in low codimension are often minimal.

Study shows how fast a specific matrix completion method works.

Efficiently completes low-rank matrices with nearly linear time complexity.

We propose a simple, scalable, and fast gradient descent algorithm to optimize a nonconvex objective for the rank minimization problem and a closely related family of semidefinite programs. With $O(r^3 κ^2 n \log n)$ random measurements of a positive semidefinite $n \times n$ matrix of rank $r$ and condition number $κ$…

As surrogate functions of $L_0$-norm, many nonconvex penalty functions have been proposed to enhance the sparse vector recovery. It is easy to extend these nonconvex penalty functions on singular values of a matrix to enhance low-rank matrix recovery. However, different from convex optimization, solving the nonconvex l…

We show the rank (i.e. minimal size of a generating set) of lattices cannot grow faster than the volume.

Study shows certain toric arrangements have minimal topological complements.

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…

This paper studies geodesics between covariance matrices of different ranks using the Bures-Wasserstein metric.

This paper considers compressed sensing and affine rank minimization in both noiseless and noisy cases and establishes sharp restricted isometry conditions for sparse signal and low-rank matrix recovery. The analysis relies on a key technical tool which represents points in a polytope by convex combinations of sparse v…

Matrix rank minimization problem is in general NP-hard. The nuclear norm is used to substitute the rank function in many recent studies. Nevertheless, the nuclear norm approximation adds all singular values together and the approximation error may depend heavily on the magnitudes of singular values. This might restrict…

ScaledGD improves gradient descent for ill-conditioned low-rank matrix estimation.

A new method for forming learning objectives using the sum of ranked range.

This paper is concerned with the factorization form of the rank regularized loss minimization problem. To cater for the scenario in which only a coarse estimation is available for the rank of the true matrix, an $\ell_{2,0}$-norm regularized term is added to the factored loss function to reduce the rank adaptively; and…

Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data. For example, for the problem of low-rank matrix completion, this method is believed to be one of the most accurate and efficient, and formed a major component of the wi…

SGD and weight decay encourage neural networks to learn low-rank weight matrices.

A new method for 1-bit matrix completion that is faster and more accurate.

Given a limited number of entries from the superposition of a low-rank matrix plus the product of a known fat compression matrix times a sparse matrix, recovery of the low-rank and sparse components is a fundamental task subsuming compressed sensing, matrix completion, and principal components pursuit. This paper devel…

Rank minimization (RM) is a wildly investigated task of finding solutions by exploiting low-rank structure of parameter matrices. Recently, solving RM problem by leveraging non-convex relaxations has received significant attention. It has been demonstrated by some theoretical and experimental work that non-convex relax…

New algorithm improves tensor completion performance.

Alternating Minimization is a widely used and empirically successful heuristic for matrix completion and related low-rank optimization problems. Theoretical guarantees for Alternating Minimization have been hard to come by and are still poorly understood. This is in part because the heuristic is iterative and non-conve…

Paper tackles low-rank matrix recovery with column $\ell_{2,0}$-norm regularization.

Nuclear norm minimization (NNM) has recently gained significant attention for its use in rank minimization problems. Similar to compressed sensing, using null space characterizations, recovery thresholds for NNM have been studied in \cite{arxiv,Recht_Xu_Hassibi}. However simulations show that the thresholds are far fro…