paper-with-me

홈 › Papers

Unified Scalable Equivalent Formulations for Schatten Quasi-Norms

2016-06-02 · Fanhua Shang, Yuanyuan Liu, James Cheng

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 problems, due to the SVD or EVD of the whole matrix in each iteration. In this paper, we rigorously prove that for any p, p1, p2>0 satisfying 1/p=1/p1+1/p2, the Schatten-p quasi-norm of any matrix is equivalent to minimizing the product of the Schatten-p1 norm (or quasi-norm) and Schatten-p2 norm (or quasi-norm) of its two factor matrices. Then we present and prove the equivalence relationship between the product formula of the Schatten quasi-norm and its weighted sum formula for the two cases of p1 and p2: p1=p2 and p1\neq p2. In particular, when p>1/2, there is an equivalence between the Schatten-p quasi-norm of any matrix and the Schatten-2p norms of its two factor matrices, where the widely used equivalent formulation of the nuclear norm can be viewed as a special case. That is, various SQNM problems with p>1/2 can be transformed into the one only involving smooth, convex norms of two factor matrices, which can lead to simpler and more efficient algorithms than conventional methods. We further extend the theoretical results of two factor matrices to the cases of three and more factor matrices, from which we can see that for any 0<p<1, the Schatten-p quasi-norm of any matrix is the minimization of the mean of the Schatten-(p3+1)p norms of all factor matrices, where p3 denotes the largest integer not exceeding 1/p. In other words, for any 0<p<1, the SQNM problem can be transformed into an optimization problem only involving the smooth, convex norms of multiple factor matrices.

📄 PDF Abstract BibTeX arXiv:1606.00668

Code (0)

등록된 구현이 없습니다.

Similar Papers 제목 키워드 기반

Scalable Algorithms for Tractable Schatten Quasi-Norm Minimization

2016-06-04 · Fanhua Shang, Yuanyuan Liu, James Cheng

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 …

Matrix Completion

Tractable and Scalable Schatten Quasi-Norm Approximations for Rank Minimization

2018-02-28 · Fanhua Shang, Yuanyuan Liu, James Cheng

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

Euclidean-Norm-Induced Schatten-p Quasi-Norm Regularization for Low-Rank Tensor Completion and Tensor Robust Principal Component Analysis

2020-12-07 · Jicong Fan, Lijun Ding, Chengrun Yang, Zhao Zhang 외

The nuclear norm and Schatten-$p$ quasi-norm are popular rank proxies in low-rank matrix recovery. However, computing the nuclear norm or Schatten-$p$ quasi-norm of a tensor is hard in both theory and practice, hindering…

EquivaMap: Leveraging LLMs for Automatic Equivalence Checking of Optimization Formulations

2025-02-20 · Haotian Zhai, Connor Lawless, Ellen Vitercik, Liu Leqi

A fundamental problem in combinatorial optimization is identifying equivalent formulations. Despite the growing need for automated equivalence checks -- driven, for example, by optimization copilots, which generate probl…

Combinatorial Optimizationvalid

Performance Guarantees for Schatten-$p$ Quasi-Norm Minimization in Recovery of Low-Rank Matrices

2014-07-14 · Mohammadreza Malek-Mohammadi, Massoud Babaie-Zadeh, Mikael Skoglund

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…

Automated Theorem Proving