arXiv research

The Schatten quasi-norm can be used to bridge the gap between the nuclear norm and rank function, and is the tighter approximation to matrix rank. However, most existing Schatten quasi-norm minimization (SQNM) algorithms, as well as for nuclear norm minimization, are too slow or even impractical for large-scale problem…

The Schatten-p quasi-norm $(0<p<1)$ is usually used to replace the standard nuclear norm in order to approximate the rank function more accurately. However, existing Schatten-p quasi-norm minimization algorithms involve singular value decomposition (SVD) or eigenvalue decomposition (EVD) in each iteration, and thus may…

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…

The Schatten quasi-norm was introduced to bridge the gap between the trace norm and rank function. However, existing algorithms are too slow or even impractical for large-scale problems. Motivated by the equivalence relation between the trace norm and its bilinear spectral penalty, we define two tractable Schatten norm…

The paper proposes an efficient algorithm for solving Schatten-$p$ quasi-norm problems.

Muons and random optimizers perform similarly, challenging geometric optimization theory.

New algorithms improve robust PCA for vision tasks with heavy-tailed distributions.

Proposes new $\ell_0$-based methods for low-rank sparse subspace clustering.

In this paper we study general Schatten-$p$ quasi-norm (SPQN) regularized matrix minimization problems. In particular, we first introduce a class of first-order stationary points for them, and show that the first-order stationary points introduced in [11] for an SPQN regularized $vector$ minimization problem are equiva…

Study on learnability of Schatten--von Neumann operators in learning theory.

The paper studies a special Grassmannian space and shows it's an orbit of a unitary group.

The Schatten-$p$ norm ($0<p<1$) has been widely used to replace the nuclear norm for better approximating the rank function. However, existing methods are either 1) not scalable for large scale problems due to relying on singular value decomposition (SVD) in every iteration, or 2) specific to some $p$ values, e.g., $1/…

New bounds on manifold Betti numbers derived from semigroup norms.

We introduce a new framework for optimal transport using Schatten-p regularization to recover low-rank structures.

This paper investigates analytic properties of maps between hyperbolic surfaces, focusing on best Lipschitz maps and geodesic laminations.

We discuss structured Schatten norms for tensor decomposition that includes two recently proposed norms ("overlapped" and "latent") for convex-optimization-based tensor decomposition, and connect tensor decomposition with wider literature on structured sparsity. Based on the properties of the structured Schatten norms,…

In this paper, we prove the algebraic K-theory Novikov conjecture for group algebras over the ring of Schatten class operators. The main technical tool in the proof is an explicit construction of the Connes-Chern character.

This paper analyzes implicit bias in Deep Linear Discriminant Analysis.

Two new algorithms improve robust PCA and Schatten packing.

Adding linear layers to ReLU networks favors functions with low mixed variation.

CPML efficiently learns new metrics for categorical data.

Let $p$ be an even positive integer and $U_p(H)$ be the Banach-Lie group of unitary operators $u$ which verify that $u-1$ belongs to the $p$-Schatten ideal $B_p(H)$. Let ${\cal O}$ be a smooth manifold on which $U_p(H)$ acts transitively and smoothly. Then one can endow ${\cal O}$ with a natural Finsler metric in terms…

Introduces HTV to measure function complexity in learning schemes.

Density matrices are positively semi-definite Hermitian matrices with unit trace that describe the states of quantum systems. Many quantum systems of physical interest can be represented as high-dimensional low rank density matrices. A popular problem in {\it quantum state tomography} (QST) is to estimate the unknown l…

New nonconvex regularizers improve low-rank matrix recovery efficiency and accuracy.

New bounds adaptively control spectral complexity of trained Transformers.

Singular values of a data in a matrix form provide insights on the structure of the data, the effective dimensionality, and the choice of hyper-parameters on higher-level data analysis tools. However, in many practical applications such as collaborative filtering and network analysis, we only get a partial observation.…

New pivoting strategy improves trace norm contraction in low-rank approximation.

Online learning of linear operators between infinite-dimensional spaces is possible but with limitations.

Let $L^2$ be the Lebesgue space of square-integrable functions on the unit circle. We show that the injectivity problem for Toeplitz operators is linked to the existence of geodesics in the Grassmann manifold of $L^2$. We also investigate this connection in the context of restricted Grassmann manifolds associated to $p…

A new distance metric compares probability distributions using kernel covariance operators.

We set up an abstract framework that allows the investigation of Iwasawa decompositions for involutive infinite-dimensional Lie groups modeled on Banach spaces. As an application, we construct Iwasawa decompositions for classical real or complex Banach-Lie groups associated with the Schatten ideals ${\mathfrak S}_p({\m…

Paper proposes a new tensor imputation method for spatiotemporal traffic data with missing patterns.

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 this paper, we consider low rank matrix estimation using either matrix-version Dantzig Selector $\hat{A}_λ^d$ or matrix-version LASSO estimator $\hat{A}_λ^L$. We consider sub-Gaussian measurements, $i.e.$, the measurements $X_1,\ldots,X_n\in\mathbb{R}^{m\times m}$ have $i.i.d.$ sub-Gaussian entries. Suppose $\textrm…

Let $U_c(H)={u: u is unitary and u-1 is compact}$ stand for the unitary Fredholm group. We prove the following convexity result. Denote by $d_\infty$ the rectifiable distance induced by the Finsler metric given by the operator norm in $U_c(H)$. If $u_0,u_1,u\in U_c(H)$ and the geodesic $β$ joining $u_0$ and $u_1$ in $U…

A new method for joint noise removal and trend estimation from sparse signals.

Study circumcenters in Finsler unitary groups with optimal convexity bounds.

We consider the construction of the basic bundle gerbe on SU(n) introduced by Meinrenken and show that it extends to a range of groups with unitary actions on a Hilbert space including U(n), diagonal tori and the Banach Lie group of unitary operators differing from the identity by an element of a Schatten ideal. In all…

Novel tensor perturbation bounds for orthogonal iteration methods.

Let U be an open subset of R^n. Let L^2=L^2(U,dx) and H^1_0=H^1_0(U) be the standard Lebesgue and Sobolev spaces of complex-valued functions. The aim of this paper is to study the group G of invertible operators on H^1_0 which preserve the L^2-inner product. When U is bounded and the border $\partial U$ is smooth, this…

Estimates the number of connected components in a graph from a sampled subgraph.

Let ${\mathcal S}_m$ be the set of all $m\times m$ density matrices (Hermitian positively semi-definite matrices of unit trace). Consider a problem of estimation of an unknown density matrix $ρ\in {\mathcal S}_m$ based on outcomes of $n$ measurements of observables $X_1,\dots, X_n\in {\mathbb H}_m$ (${\mathbb H}_m$ bei…

New proof shows norms can't explain deep learning's implicit regularization.

Let $A$ be a positive injective operator in a Hilbert space (\h, <,>), and denote by [,] the inner product defined by A: [f,g]=<Af,g>. A closed subspace $\s \subset \h$ is called A-compatible if there exists a closed complement for $\s$, which is orthogonal to $\s$ with respect to the inner product [,]. Equivalently, i…

Several important applications, such as streaming PCA and semidefinite programming, involve a large-scale positive-semidefinite (psd) matrix that is presented as a sequence of linear updates. Because of storage limitations, it may only be possible to retain a sketch of the psd matrix. This paper develops a new algorith…

Extended Gauss-Markov theorem for linear estimation with bounded bias.

The density matrices are positively semi-definite Hermitian matrices of unit trace that describe the state of a quantum system. The goal of the paper is to develop minimax lower bounds on error rates of estimation of low rank density matrices in trace regression models used in quantum state tomography (in particular, i…