arXiv research

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

CPML efficiently learns new metrics for categorical data.

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

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…

Two new algorithms improve robust PCA and Schatten packing.

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…

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…

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…

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

New framework for private convex optimization in arbitrary norms.

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…

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

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…

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…

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…

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.

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…

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…

Study improves image classifier robustness to random p-norm corruptions.

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…

Unified algorithm for any $p$-norm experimental design problems.

Introduces HTV to measure function complexity in learning schemes.

In this paper, we study global existence and blow up properties to $L^p$ norm preserving non-local heat flows. We first study two kinds of $L^p$ norm preserving non-local flows and prove that these flows have the global solutions. Finally, we give a example to show that one kind of this heat flow may blow up in $L^{\in…

New method improves tensor completion by selectively preserving important elements.

This work studies the implicit bias of mini-batch SGD in classification.

This paper tackles robustness of ensemble stumps and trees under general ℓ_p norm perturbations.

Proposes a new regression method using $L_p$-norms for non-Gaussian noise.

New bounds adaptively control spectral complexity of trained Transformers.

We show that for the problem of testing if a matrix $A \in F^{n \times n}$ has rank at most $d$, or requires changing an $ε$-fraction of entries to have rank at most $d$, there is a non-adaptive query algorithm making $\widetilde{O}(d^2/ε)$ queries. Our algorithm works for any field $F$. This improves upon the previous…

Adversarial attacks aim to confound machine learning systems, while remaining virtually imperceptible to humans. Attacks on image classification systems are typically gauged in terms of $p$-norm distortions in the pixel feature space. We perform a behavioral study, demonstrating that the pixel $p$-norm for any $0\le p …

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.

The paper analyzes the performance of empirical risk minimization for $p$-norm linear regression.

Paper addresses concentration of distances for fractional quasi p-norms, identifying conditions for concentration and anti-concentration.

The paper proposes a novel MKL approach for OCC using $\ell_p$-norm constraints.

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

Verifying robustness of neural networks given a specified threat model is a fundamental yet challenging task. While current verification methods mainly focus on the $\ell_p$-norm threat model of the input instances, robustness verification against semantic adversarial attacks inducing large $\ell_p$-norm perturbations,…

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…

In this paper, we propose $\ell_p$-norm regularized models to seek near-optimal sparse portfolios. These sparse solutions reduce the complexity of portfolio implementation and management. Theoretical results are established to guarantee the sparsity of the second-order KKT points of the $\ell_p$-norm regularized models…

The paper proposes a new method for dictionary learning using $\ell_p$-norm maximization.

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

We give improved algorithms for the $\ell_{p}$-regression problem, $\min_{x} \|x\|_{p}$ such that $A x=b,$ for all $p \in (1,2) \cup (2,\infty).$ Our algorithms obtain a high accuracy solution in $\tilde{O}_{p}(m^{\frac{|p-2|}{2p + |p-2|}}) \le \tilde{O}_{p}(m^{\frac{1}{3}})$ iterations, where each iteration requires s…

Max-convolution is an important problem closely resembling standard convolution; as such, max-convolution occurs frequently across many fields. Here we extend the method with fastest known worst-case runtime, which can be applied to nonnegative vectors by numerically approximating the Chebyshev norm $\| \cdot \|_\infty…