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 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 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/…

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 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,…

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…

We derive new estimates for the first Betti number of compact Riemannian manifolds. Our approach relies on the Birman-Schwinger principle and Schatten norm estimates for semigroup differences. In contrast to previous works we do not require any a priori ultracontractivity estimates and we provide bounds which explicitl…

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

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

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

New bounds adaptively control spectral complexity of trained Transformers.

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

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…

This paper develops a new class of nonconvex regularizers for low-rank matrix recovery. Many regularizers are motivated as convex relaxations of the matrix rank function. Our new factor group-sparse regularizers are motivated as a relaxation of the number of nonzero columns in a factorization of the matrix. These nonco…

Metric learning has been successful in learning new metrics adapted to numerical datasets. However, its development on categorical data still needs further exploration. In this paper, we propose a method, called CPML for \emph{categorical projected metric learning}, that tries to efficiently~(i.e. less computational ti…

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

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…

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.…

Two new algorithms improve robust PCA and Schatten packing.

The heavy-tailed distributions of corrupted outliers and singular values of all channels in low-level vision have proven effective priors for many applications such as background modeling, photometric stereo and image alignment. And they can be well modeled by a hyper-Laplacian. However, the use of such distributions g…

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…

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

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.

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

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

Novel tensor perturbation bounds for orthogonal iteration methods.

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

Muon dynamics study uses spectral Wasserstein flow for optimization stability.

Study circumcenters in Finsler unitary groups with optimal convexity bounds.

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

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…

New framework for private convex optimization in arbitrary 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.

We study the learnability of a class of compact operators known as Schatten--von Neumann operators. These operators between infinite-dimensional function spaces play a central role in a variety of applications in learning theory and inverse problems. We address the question of sample complexity of learning Schatten-von…

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…

In many applications, high-dimensional data points can be well represented by low-dimensional subspaces. To identify the subspaces, it is important to capture a global and local structure of the data which is achieved by imposing low-rank and sparseness constraints on the data representation matrix. In low-rank sparse …

Goal: This paper deals with the problems that some EEG signals have no good sparse representation and single channel processing is not computationally efficient in compressed sensing of multi-channel EEG signals. Methods: An optimization model with L0 norm and Schatten-0 norm is proposed to enforce cosparsity and low r…

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…

Paper optimizes private PCA for covariance estimation in statistics.

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…

Muon optimizes Transformer training with heavy-tailed data, achieving optimal sample complexity.

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…

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…

We develop a novel family of algorithms for the online learning setting with regret against any data sequence bounded by the empirical Rademacher complexity of that sequence. To develop a general theory of when this type of adaptive regret bound is achievable we establish a connection to the theory of decoupling inequa…

New method improves tensor completion by selectively preserving important elements.

Let $U_2({\cal H})$ be the Banach-Lie group of unitary operators in the Hilbert space ${\cal H}$ which are Hilbert-Schmidt perturbations of the identity 1. In this paper we study the geometry of the unitary orbit $\{upu^*: u\in U_2({\cal H})\},$ of an infinite projection $p$ in ${\cal H}$. This orbit coincides with t…

New method for robust matrix completion with mixed data types.