A Unified Scalable Equivalent Formulation for Schatten Quasi-Norms

Abstract

The Schatten quasi-norm is an approximation of the rank, which is tighter than the nuclear norm. However, most Schatten quasi-norm minimization (SQNM) algorithms suffer from high computational cost to compute the singular value decomposition (SVD) of large matrices at each iteration. In this paper, we prove that for any p, $p_1$, $p_2>0$ satisfying $1/p=1/p_1+1/p_2$, the Schatten p-(quasi-)norm of any matrix is equivalent to minimizing the product of the Schatten $p_1$-(quasi-)norm and Schatten $p_2$-(quasi-)norm of its two much smaller factor matrices. Then, we present and prove the equivalence between the product and its weighted sum formulations for two cases: $p_1=p_2$ and $p_1\ne p_2$. 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. 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 $(\lfloor 1/p\rfloor +1)p$-norms of $\lfloor 1/p\rfloor +1$ factor matrices, where $\lfloor 1/p\rfloor$ denotes the largest integer not exceeding $1/p$.

1. Introduction

The affine rank minimization problem arises directly in various areas of science and engineering, including statistics, machine learning, information theory, data mining, medical imaging, and computer vision. Some representative applications include matrix completion [1], robust principal component analysis (RPCA) [2], low-rank representation [3], multivariate regression [4], multi-task learning [5], and system identification [6]. To efficiently solve such problems, we mainly relax the rank function to its tractable convex envelope, that is, the nuclear norm ${\parallel ·\parallel }_{\ast }$ (sum of the singular values, also known as the trace norm or Schatten 1-norm), which leads to a convex optimization problem [1,7,8,9]. In fact, the nuclear norm of a matrix is the ${\ell }_1$-norm of the vector of its singular values, and thus it can motivate a low-rank solution. However, it has been shown in [10,11] that the ${\ell }_1$-norm over-penalizes large entries of vectors and therefore results in a solution from a possibly biased solution space. Recall from the relationship between the ${\ell }_1$-norm and nuclear norm that the nuclear norm penalty shrinks all singular values equally, which also leads to the over-penalization of large singular values [12]. That is, the nuclear norm may make the solution deviate from the original solution as the ${\ell }_1$-norm does. Unlike the nuclear norm, the Schatten p-quasi-norm with $0<p<1$ is non-convex, and it can give a closer approximation to the rank function. Thus, the Schatten quasi-norm minimization (SQNM) has received a significant amount of attention from researchers in various communities, such as image recovery [13], collaborative filtering [14,15], and MRI analysis [16].

Recently, several iteratively re-weighted least squares (IRLS) algorithms as in [17,18] have been proposed to approximately solve associated Schatten quasi-norm minimization problems. Lu et al. [13] proposed a family of iteratively re-weighted nuclear norm (IRNN) algorithms to solve various non-convex surrogate (including the Schatten quasi-norm) minimization problems. In [13,14,19,20], the Schatten quasi-norm has been shown to be empirically superior to the nuclear norm for many real-world problems. Moreover, [21] theoretically proved that the SQNM requires significantly fewer measurements than nuclear norm minimization as in [1,9]. However, all the algorithms have to be solved iteratively and involve singular value decomposition (SVD) in each iteration. Thus, they suffer from a high computational complexity of $O(min(m,n\left)mn\right)$ and are not applicable for large-scale matrix recovery problems [22].

It is well known that the nuclear norm has a scalable equivalent formulation (also called the bilinear spectral penalty [9,23,24]), which has been successfully applied in many applications, such as collaborative filtering [15,25,26]. Zuo et al. [27] proposed a generalized shrinkage-thresholding operator to iteratively solve ${\ell }_p$ quasi-norm minimization with $0\le p<1$. Since the Schatten p-quasi-norm of one matrix is equivalent to the ${\ell }_p$ quasi-norm on its singular values, we may naturally ask the following question: can we design a unified scalable equivalent formulation to the Schatten p-quasi-norm with arbitrary p values (i.e., $0<p<1$)?

In this paper (note that the first version [28] of this paper appeared on ArXiv, and in the current version we have included experimental results and fixed a few typos.), we first present and prove the equivalence relation on the Schatten p-(quasi-)norm of any matrix and minimization of the product of the Schatten $p_1$-(quasi-)norm and Schatten $p_2$-(quasi-)norm of its two smaller factor matrices, for any p, $p_1$, $p_2>0$ satisfying $1/p=1/p_1+1/p_2$. Moreover, we prove the equivalence between the product formulation of the Schatten (quasi-)norm and its weighted sum formulation for the two cases of $p_1$ and $p_2$: $p_1=p_2$ and $p_1\ne p_2$. When $p>1/2$ and by setting the same value for $p_1$ and $p_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 a representative example is the equivalent formulation of the nuclear norm, i.e.,

$${\parallel X\parallel }_{\ast }=\underset{X=U{V}^T}{min}\frac{{\parallel U\parallel }_F^2+{\parallel V\parallel }_F^2}{2}.$$

That is, the SQNM problems with $p>1/2$ can be transformed into problems only involving the smooth convex norms of two factor matrices, which can lead to simpler and more efficient algorithms (e.g., [12,22,29,30]). Clearly, the resulting algorithms can reduce the per-iteration cost from $O(min(m,n\left)mn\right)$ to $O\left(mnd\right)$, where $d\ll m,n$ in general.

We further extend the theoretical results of two factor matrices to the cases of three and more factor matrices, from which we can know that for any $0<p<1$, the Schatten p-quasi-norm of any matrix is equivalent to the minimization of the mean of the Schatten $(\lfloor 1/p\rfloor +1)p$-norms of $\lfloor 1/p\rfloor +1$ factor matrices, where $\lfloor 1/p\rfloor$ denotes the largest integer not exceeding $1/p$. Note that the norms of all the smaller factor matrices are convex and smooth. Besides the theoretical results, we also present several representative examples for two and three factor matrices. In fact, the bi-nuclear and Frobenius/nuclear quasi-norms defined in our previous work [22] and the tri-nuclear quasi-norm defined in our previous work [29] are three important special cases of our unified scalable formulations for Schatten quasi-norms.

2. Notations and Background

In this section, we present the definition of the Schatten p-norm and discuss some related work about Schatten p-norm minimization. We first briefly recall the definitions of both the norm and the quasi-norm.

Definition 1.

A quasi-norm $\parallel ·\parallel$ on a vector space X is a real-valued map $X\to [0,\infty )$ with the following conditions:

• $\parallel x\parallel \ge 0$ for any vector $x\in X$, and $\parallel x\parallel =0$ if and only if $x=0$.
• $\parallel \alpha x\parallel =\left|\alpha \right|\parallel x\parallel$ if $\alpha \in ℝ$ or $ℂ$, and $x\in X$.
• There is a constant $c\ge 1$ so that if $x_1,x_2\in X$ we have $\parallel x_1+x_2\parallel \le c(\parallel x_1\parallel +\parallel x_2\parallel )$ (triangle inequality).

If the triangle inequality is replaced by $\parallel x_1+x_2\parallel \le \parallel x_1\parallel +\parallel x_2\parallel$, then it becomes a norm.

Definition 2.

The Schatten p-norm ($0<p<\infty$) of a matrix $X\in {\mathbb{R}}^{m\times n}$ (without loss of generality, we assume that $m\ge n$) is defined as

$${\parallel X\parallel }_{S_p}={\left(\sum _{i=1}^n{\sigma }_i^p\left(X\right)\right)}^{1/p},$$

(1)

where ${\sigma }_i\left(X\right)$ denotes the i-th singular value of X.

When $p\ge 1$, Definition 2 defines a natural norm, whereas it defines a quasi-norm for $0<p<1$. For instance, the Schatten 1-norm is the so-called nuclear norm, ${\parallel X\parallel }_{\ast }$, and the Schatten 2-norm is the well-known Frobenius norm, ${\parallel X\parallel }_F=\sqrt{{\sum }_{i=1}^m{\sum }_{j=1}^n{x}_{ij}^2}$. As the non-convex surrogate for the rank function, the Schatten p-quasi-norm is the better approximation than the nuclear norm [21], analogous to the superiority of the ${\ell }_p$ quasi-norm to the ${\ell }_1$-norm [18,31].

To recover a low-rank matrix from a small set of linear observations, $b\in {\mathbb{R}}^l$, the general SQNM problem is formulated as follows:

$$\underset{X\in {\mathbb{R}}^{m\times n}}{min}{\parallel X\parallel }_{S_p}^p,\mathrm{subject}\mathrm{to}\mathcal{A}\left(X\right)=b,$$

(2)

where $\mathcal{A}:{\mathbb{R}}^{m\times n}\to {\mathbb{R}}^l$ is a general linear operator. Alternatively, the Lagrangian version of (2) is

$$\underset{X\in {\mathbb{R}}^{m\times n}}{min}\left\{{\lambda \parallel X\parallel }_{S_p}^p+f\left(\mathcal{A}\left(X\right)-b\right)\right\},$$

(3)

where $\lambda >0$ is a regularization parameter, and $f(·):{\mathbb{R}}^l\to \mathbb{R}$ denotes a certain measurement for characterizing the loss $\left(\mathcal{A}\right(X)-b)$. For instance, $\mathcal{A}$ is the projection operator ${\mathcal{P}}_{\Omega }$, and $f(·)={\parallel ·\parallel }_2^2$ in matrix completion [13,17,20,32], where ${\mathcal{P}}_{\Omega }$ is the orthogonal projection onto the linear subspace of matrices supported on $\Omega :=\left\{(i,j)\right|D_{ij}\mathrm{is}\mathrm{observed}\}$, that is, ${\mathcal{P}}_{\Omega }{\left(D\right)}_{ij}=D_{ij}$ if $(i,j)\in \Omega$, and ${\mathcal{P}}_{\Omega }{\left(D\right)}_{ij}=0$ otherwise. For RPCA problems [2,33,34,35,36], $\mathcal{A}$ is an identity operator and $f(·)={\parallel ·\parallel }_1$. In the multivariate regression problem in [37], $\mathcal{A}\left(X\right)=AX$ with A being a given matrix, and $f(·)={\parallel ·\parallel }_F^2$. In addition, $f(·)$ may be chosen as the Hinge loss in [23] or the ${\ell }_p$ quasi-norm in [14].

Generally, SQNM problems (e.g., (2) and (3)) are non-convex, non-smooth, and even non-Lipschitz [38]. So far, only a few algorithms (e.g., IRLS [17,18] and IRNN [13]) have been developed to solve such challenging problems. However, since the SQNM algorithms involve SVD of large matrices in each iteration, they suffer from a high computational cost of $O\left(m{n}^2\right)$, which severely limits their applicability to large-scale problems. While there have been many efforts towards fast SVD computation such as partial SVD [39], the performances of these methods are still unsatisfactory for many real applications [40]. As an alternative to reduce the computational complexity of SVD on a large matrix, one can factorize X into two smaller factor matrices (i.e., $X=U{V}^T$). According to the unitary invariant property of norms, (2) and (3) can be reformulated into two much smaller matrix optimization problems as in [23,41,42,43,44], which are still non-convex and non-smooth. Therefore, it is very important to determine how to transform challenging problems such as (2) and (3) into more tractable ones, which can be solved by simpler and more efficient algorithms as in [30,43].

3. A Unified Formulation for Schatten Quasi-Norms

In this section, we first present and prove an equivalence relation on the Schatten p-(quasi-)norm of any matrix and the Schatten $p_1$-(quasi-)norm and Schatten $p_2$-(quasi-)norm of its two factor matrices, where $1/p=1/p_1+1/p_2$ with any $p_1>0$ and $p_2>0$. Moreover, we prove the equivalence between the product formulation of the Schatten (quasi-)norm and its weighted sum formulation for the two cases: $p_1=p_2$ and $p_1\ne p_2$, respectively. For any $1/2<p\le 1$, the Schatten p-(quasi-)norm of any matrix is equivalent to minimizing the mean of the Schatten $2p$-norms of both factor matrices, which can lead to simpler and more efficient algorithms. Finally, we extend the theoretical results of two factor matrices to the cases of three and more factor matrices. One 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 $(\lfloor 1/p\rfloor +1)p$-norms of $\lfloor 1/p\rfloor +1$ factor matrices.

3.1. Unified Schatten Quasi-Norm Formulations of Two Factor Matrices

In this subsection, we present some unified Schatten quasi-norm scalable formulations for the case of two factor matrices.

Theorem 1.

Each matrix $X\in {\mathbb{R}}^{m\times n}$ with $rank\left(X\right)=r\le d$ can be decomposed into the product of two much smaller matrices $U\in {\mathbb{R}}^{m\times d}$ and $V\in {\mathbb{R}}^{n\times d}$, i.e., $X=U{V}^T$. For any $0<p\le 1$, $p_1>0$ and $p_2>0$ satisfying $1/p_1+1/p_2=1/p$, we have

$${\parallel X\parallel }_{S_p}=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}.$$

(4)

The proof of Theorem 1 is provided in Section 5.1. From Theorem 1, it is clear that for any $0<p\le 1$ and $p_1,p_2>0$ satisfying $1/p=1/p_1+1/p_2$, the Schatten p-(quasi-)norm of any matrix X is equivalent to minimizing the product of the Schatten $p_1$-(quasi-)norm and Schatten $p_2$-(quasi-)norm of its two factor matrices.

In fact, we can find that $p_1$ and $p_2$ may have the same value (i.e., $p_1=p_2=2p$) or different values (i.e., $p_1\ne p_2$). Next, we discuss the two cases for $p_1$ and $p_2$, that is, $p_1=p_2$ and $p_1\ne p_2$.

3.1.1. The Case of $p_1=p_2$

We first discuss the case when $p_1=p_2$. In fact, for any given $0<p\le 1$, there exist infinitely many pairs of positive numbers $p_1$ and $p_2$ satisfying $1/p_1+1/p_2=1/p$, such that the equality (4) holds. By setting the same value for $p_1$ and $p_2$ (i.e., $p_1=p_2=2p$), we give a unified scalable equivalent formulation for the Schatten p-(quasi-)norm as follows.

Theorem 2.

Given any matrix $X\in {\mathbb{R}}^{m\times n}$ of $rank\left(X\right)=r\le d$, then the following equalities hold:

$$\begin{array}{c}\hfill {\parallel X\parallel }_{S_p}=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{S_{2p}}{\parallel V\parallel }_{S_{2p}}=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\left(\frac{{\parallel U\parallel }_{S_{2p}}^{2p}+{\parallel V\parallel }_{S_{2p}}^{2p}}{2}\right)}^{1/p}.\end{array}$$

(5)

Remark 1.

The proof of Theorem 2 is provided in Section 5.2. From the equality in (5), we know that for any $0<p\le 1$, the Schatten p-(quasi-)norm minimization problems in many low-rank matrix completion and recovery applications can be transformed into the problems of minimizing the mean of the Schatten $2p$-(quasi-)norms of two smaller factor matrices. It should be noted that when $1/2<p\le 1$, the norms of two smaller factor matrices are convex and smooth (see Example 2 below) due to $2p>1$, which can lead to simpler and more efficient algorithms as in [43].

When $p=1$ and $p_1=p_2=2$, the equalities in Theorem 2 become the following form [23].

Corollary 1.

Given any matrix $X\in {\mathbb{R}}^{m\times n}$ with $rank\left(X\right)=r\le d$, the following equalities hold:

$$\begin{array}{c}\hfill {\parallel X\parallel }_{\ast }=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_F{\parallel V\parallel }_F=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}\frac{1}{2}{(\parallel U\parallel }_F^2+{\parallel V\parallel }_F^2).\end{array}$$

(6)

The bilinear spectral penalty in (6) has been widely used in many low-rank matrix completion and recovery problems, such as collaborative filtering [9,23], RPCA [45], online RPCA [46], and image recovery [47]. Note that the well-known equivalent formulation of the nuclear norm in Corollary 1 is just a special case of Theorem 2 when $p=1$ and $p_1=p_2=2$. Moreover, we give two more representative examples for the case of $p_1=p_2$.

Example 1.

When $p=1/2$, and by setting $p_1=p_2=1$ and using Theorem 1, we have the following property, as in our previous work [22,29].

Property 1.

For any matrix $X\in {\mathbb{R}}^{m\times n}$ with $rank\left(X\right)=r\le d$, the following equalities hold:

$$\begin{array}{c}\hfill {\parallel X\parallel }_{S_{1/2}}=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{\ast }{\parallel V\parallel }_{\ast }=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\left(\frac{{\parallel U\parallel }_{\ast }+{\parallel V\parallel }_{\ast }}{2}\right)}^2.\end{array}$$

(7)

In [22,29], the scalable formulations in the above equalities are known as the bi-nuclear quasi-norm. In other words, the bi-nuclear quasi-norm is also a special case of Theorem 2 when $p=1/2$ and $p_1=p_2=1$.

Example 2.

When $p=2/3$, and by setting $p_1=p_2=4/3$ and using Theorem 1, we have the following property.

Property 2.

For any matrix $X\in {\mathbb{R}}^{m\times n}$ with $rank\left(X\right)=r\le d$, the following equalities hold:

$$\begin{array}{c}\hfill {\parallel X\parallel }_{S_{2/3}}=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{S_{4/3}}{\parallel V\parallel }_{S_{4/3}}=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\left(\frac{{\parallel U\parallel }_{S_{4/3}}^{4/3}+{\parallel V\parallel }_{S_{4/3}}^{4/3}}{2}\right)}^{3/2}.\end{array}$$

3.1.2. The Case of $p_1\ne p_2$

In this part, we discuss the case of $p_1\ne p_2$. Unlike the case of $p_1=p_2$, we may set infinitely many different values for $p_1$ and $p_2$. For any given $0<p\le 1$, there must exist $p_1,p_2>0$, at least one of which is no less than 1, such that $1/p=1/p_1+1/p_2$. Indeed, for any $0<p\le 1$, the values of $p_1$ and $p_2$ may be different (e.g., $p_1=1$ and $p_2=2$ for $p=2/3$), and thus we give the following unified scalable equivalent formulations for the Schatten p-(quasi-)norm. Note that after our work [28] appeared on ArXiv, [12] also presented the same result independently as in Theorem 3.

Theorem 3.

Given any matrix $X\in {\mathbb{R}}^{m\times n}$ of $rank\left(X\right)=r\le d$, and any $0<p\le 1$, $p_1>0$ and $p_2>0$ satisfying $1/p_1+1/p_2=1/p$, then the following equalities hold:

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}& =\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}\hfill \\ \hfill & =\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\left(\frac{p_2{\parallel U\parallel }_{S_{p_1}}^{p_1}+p_1{\parallel V\parallel }_{S_{p_2}}^{p_2}}{p_1+p_2}\right)}^{1/p}\hfill \\ \hfill & =\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\left(\frac{{\parallel U\parallel }_{S_{p_1}}^{p_1}/p_1+{\parallel V\parallel }_{S_{p_2}}^{p_2}/p_2}{1/p}\right)}^{1/p}.\hfill \end{array}$$

(8)

Remark 2.

The proof of Theorem 3 is given in Section 5.3. From Theorem 3, we know that Theorem 2 and Corollary 1 can be viewed as two special cases of Theorem 3 when $p_1=p_2=2p$ and $p_1=p_2=2$, respectively. That is, Theorem 3 is the more general form of Theorem 2 and Corollary 1. From the equality in (8), we can see that for any $0<p\le 1$, the Schatten p-(quasi-)norm minimization problem can be transformed into the one of minimizing the weighted sum of the Schatten $p_1$-(quasi-)norm and Schatten $p_2$-(quasi-)norm of two smaller factor matrices (see Examples 3 and 4 below), where the weights of the two terms are $p_2/(p_1+p_2)$ and $p_1/(p_1+p_2)$, respectively.

Below we give two representative examples for the case of $p_1\ne p_2$.

Example 3.

When $p=2/3$, and by setting $p_1=1$ and $p_2=2$, we have the following property, as in our previous work [22].

Property 3.

Given any matrix $X\in {\mathbb{R}}^{m\times n}$ with $rank\left(X\right)=r\le d$, the following equalities hold:

$$\begin{array}{c}\hfill {\parallel X\parallel }_{S_{2/3}}=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{\ast }{\parallel V\parallel }_F=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\left(\frac{{2\parallel U\parallel }_{\ast }+{\parallel V\parallel }_F^2}{3}\right)}^{3/2}.\end{array}$$

(9)

The scalable formulation in (9) is known as the Frobenius/nuclear hybrid quasi-norm defined in our previous work [22]. It is clear that the Frobenius/nuclear hybrid quasi-norm is also a special case of Theorem 3 when $p=2/3$, $p_1=1$, and $p_2=2$. As shown in [22,29], we can design more efficient algorithms to solve the Schatten p-quasi-norm minimization with $1/2\le p<1$.

Example 4.

When $p=2/5$, and by setting $p_1=1/2$ and $p_2=2$, we have the following property.

Property 4.

Given any matrix $X\in {\mathbb{R}}^{m\times n}$ with $rank\left(X\right)=r\le d$, the following equalities hold:

$$\begin{array}{c}\hfill {\parallel X\parallel }_{S_{2/5}}=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{S_{1/2}}{\parallel V\parallel }_F=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\left(\frac{{4\parallel U\parallel }_{S_{1/2}}^{1/2}+{\parallel V\parallel }_F^2}{5}\right)}^{5/2}.\end{array}$$

3.2. Extensions to Multiple Factor Matrices

In this subsection, we extend the unified Schatten quasi-norm formulations of two factor matrices to the case of multiple factor matrices.

Theorem 4.

Each matrix $X\in {\mathbb{R}}^{m\times n}$ of $rank\left(X\right)=r\le d$ can be decomposed into the product of three much smaller matrices $U\in {\mathbb{R}}^{m\times d}$, $V\in {\mathbb{R}}^{d\times d}$ and $W\in {\mathbb{R}}^{n\times d}$, that is, $X=UV{W}^T$. For any $0<p\le 1$ and $p_i>0$ for all $i=1,2,3$, satisfying $1/p_1+1/p_2+1/p_3=1/p$, then

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}=& \underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{d\times d},W\in {\mathbb{R}}^{n\times d}:X=UV{W}^T}{min}{\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}{\parallel W\parallel }_{S_{p_3}}\hfill \\ \hfill =& \underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{d\times d},W\in {\mathbb{R}}^{n\times d}:X=UV{W}^T}{min}{\left(\frac{{\parallel U\parallel }_{S_{p_1}}^{p_1}/p_1+{\parallel V\parallel }_{S_{p_2}}^{p_2}/p_2+{\parallel W\parallel }_{S_{p_3}}^{p_3}/p_3}{1/p}\right)}^{1/p}.\hfill \end{array}$$

(10)

The proof of Theorem 4 is provided in Section 5.4. From Theorem 4, one can see that for any $0<p\le 1$ and $p_1,p_2,p_3>0$ satisfying $1/p_1+1/p_2+1/p_3=1/p$, the Schatten p-(quasi-)norm of any matrix is equivalent to minimizing the weighted sum of the Schatten $p_1$-(quasi-)norm, Schatten $p_2$-(quasi-)norm, and Schatten $p_3$-(quasi-)norm of the three smaller factor matrices, where the weights of the three terms are $p/p_1$, $p/p_2$, and $p/p_3$, respectively. Similarly, we extend the results in Theorem 4 to the case of more factor matrices as follows.

Theorem 5.

Each matrix $X\in {\mathbb{R}}^{m\times n}$ of $rank\left(X\right)=r\le d$ can be decomposed into the product of multiple much smaller matrices $U_i$, $i=1,2,\dots ,M$ (i.e., $X={\prod }_{i=1}^M{U}_i$). For any $0<p\le 1$ and $p_i>0$ for all $i=1,2,\dots ,M$, satisfying ${\sum }_{i=1}^{M}1/p_i=1/p$, then

$$\begin{array}{c}\hfill {\parallel X\parallel }_{S_p}=\underset{U_i:X={\prod }_{i=1}^M{U}_i}{min}\prod _{i=1}^M{\parallel U_i\parallel }_{S_{p_i}}=\underset{U_i:X={\prod }_{i=1}^M{U}_i}{min}{\left(\frac{{\sum }_{i=1}^M{\parallel U_i\parallel }_{S_{p_i}}^{p_i}/p_i}{1/p}\right)}^{1/p}.\end{array}$$

(11)

The proof of Theorem 5 is very similar to that of Theorem 4, and is thus omitted. From Theorem 5, we can know that for any $0<p\le 1$ and $p_i>0$ for all $i=1,2,\dots ,M$ satisfying ${\sum }_{i=1}^{M}1/p_i=1/p$, the Schatten p-(quasi-)norm of any matrix is equivalent to minimizing the weighted sum of the Schatten $p_i$-(quasi-)norms of the smaller factor matrices, where the weights for these terms are $p/p_i$ for all $i=1,2,\dots ,M$.

Similar to the case of two factor matrices, for any given $0<p\le 1$, there exist infinitely many positive numbers $p_1$, $p_2$, and $p_3$ such that $1/p_1+1/p_2+1/p_3=1/p$, and the equality (10) holds. By setting the same value for $p_1$, $p_2$, and $p_3$ (i.e., $p_1=p_2=p_3=3p$), we give the following unified scalable equivalent formulations for the Schatten p-(quasi-)norm.

Corollary 2.

Given any matrix $X\in {\mathbb{R}}^{m\times n}$ of $rank\left(X\right)=r\le d$, then the following equalities hold:

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}=& \underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{d\times d},W\in {\mathbb{R}}^{n\times d}:X=UV{W}^T}{min}{\parallel U\parallel }_{S_{3p}}{\parallel V\parallel }_{S_{3p}}{\parallel W\parallel }_{S_{3p}}\hfill \\ \hfill =& \underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{d\times d},W\in {\mathbb{R}}^{n\times d}:X=UV{W}^T}{min}{\left(\frac{{\parallel U\parallel }_{S_{3p}}^{3p}+{\parallel V\parallel }_{S_{3p}}^{3p}+{\parallel W\parallel }_{S_{3p}}^{3p}}{3}\right)}^{1/p}.\hfill \end{array}$$

(12)

Remark 3.

The proof of Corollary 2 is provided in Section 5.5. From the equality in (12), we know that for any $0<p<1$, Schatten p-quasi-norm minimization can be transformed into the problem of minimizing the mean of the Schatten $3p$-norms (or quasi-norms) of three much smaller factor matrices. We also note that when $1/3<p\le 1$, the norms of the three factor matrices are convex and smooth because $3p>1$, which can also lead to some simpler and more efficient algorithms.

Example 5.

Below we give a representative example. When $p=1/3$ and $p_1=p_2=p_3=1$, the equalities in Corollary 2 become the following forms, as in our previous work [29].

Property 5.

For any matrix $X\in {\mathbb{R}}^{m\times n}$ of $rank\left(X\right)=r\le d$, the following equalities hold:

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_{1/3}}=& \underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{d\times d},W\in {\mathbb{R}}^{n\times d}:X=UV{W}^T}{min}{\parallel U\parallel }_{\ast }{\parallel V\parallel }_{\ast }{\parallel W\parallel }_{\ast }\hfill \\ \hfill =& \underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{d\times d},W\in {\mathbb{R}}^{n\times d}:X=UV{W}^T}{min}{\left(\frac{{\parallel U\parallel }_{\ast }+{\parallel V\parallel }_{\ast }+{\parallel W\parallel }_{\ast }}{3}\right)}^3.\hfill \end{array}$$

(13)

From Property 5, we can see that the tri-nuclear quasi-norm defined in our previous work [29] is also a special case of Corollary 2.

Theorem 2 shows that for any p satisfying $1/2<p\le 1$, the Schatten p-(quasi-)norm of any matrix is equivalent to minimizing the mean of the Schatten $2p$-norms of both much smaller factor matrices, as well as Corollary 2 for any p satisfying $1/3<p\le 1$. In other words, if $1/2<p\le 1$ or $1/3<p\le 1$, Schatten p-(quasi-)norm minimization can be transformed into a simpler problem only involving the convex and smooth norms of two or three smaller factor matrices. Moreover, we extend the results of Theorem 2 and Corollary 2 to the case of more factor matrices, as shown in Corollary 3 below. The proof of Corollary 3 is very similar to that of Corollary 2, and is thus omitted. That is, for any $0<p<1$, the Schatten p-quasi-norm of any matrix can theoretically be equivalent to the minimization of the mean of the Schatten $\left(Mp\right)$-norms of all M factor matrices, where $M=(\lfloor 1/p\rfloor +1)$. It needs to be strongly emphasized that the norms of all factor matrices are convex and smooth due to $Mp>1$, which can help us to design simpler and more efficient algorithms.

Corollary 3.

Given any matrix $X\in {\mathbb{R}}^{m\times n}$ of $rank\left(X\right)=r\le d$, the following equalities hold:

$$\begin{array}{c}\hfill {\parallel X\parallel }_{S_p}=\underset{U_i:X={\prod }_{i=1}^M{U}_i}{min}\prod _{i=1}^M{\parallel U_i\parallel }_{S_{Mp}}=\underset{U_i:X={\prod }_{i=1}^M{U}_i}{min}{\left(\frac{{\sum }_{i=1}^M{\parallel U_i\parallel }_{S_{Mp}}^{Mp}}{M}\right)}^{1/p}.\end{array}$$

(14)

4. Numerical Experiments

We conducted numerical experiments to evaluate the performance of our scalable Schatten quasi-norm formulations. For a simple reason, we only briefly consider the following bi-nuclear (BN) quasi-norm and Frobenius/nuclear (FN) quasi-norm regularized least-squares problems:

$$\begin{array}{c}\hfill \underset{U,V}{min}\left\{\frac{\lambda }{2}{(\parallel U\parallel }_{\ast }+{\parallel V\parallel }_{\ast })+\frac{1}{2}{\parallel {\mathcal{P}}_{\Omega }(U{V}^T-D)\parallel }_F^2\right\},\\ \hfill \underset{U,V}{min}\left\{\frac{\lambda }{3}{(2\parallel U\parallel }_{\ast }+{\parallel V\parallel }_F^2)+\frac{1}{2}{\parallel {\mathcal{P}}_{\Omega }(U{V}^T-D)\parallel }_F^2\right\}.\end{array}$$

Here we introduce the alternating direction method of multipliers (ADMM) for solving the above two scalable Schatten quasi-norm minimization models as in [43]. We compared our BN and FN methods with existing state-of-the-art methods such as weighted nuclear norm minimization (WNNM) [48] (http://www4.comp.polyu.edu.hk/~cslzhang/) and iteratively re-weighted nuclear norm (IRNN) [49], which usually have better performance than traditional nuclear norm solvers such as [50]. As suggested in [13], we chose the ${\ell }_q$-norm penalty, where q was chosen from the range of $\{0.1,0.2,\dots ,1\}$. That is, IRNN is one Schatten q-quasi-norm minimization method. The source code of IRNN can be downloaded at the link: https://sites.google.com/site/canyilu/. We selected the same values for the parameters d, $\rho$, and ${\mu }_0$ for both our methods (e.g., $d=9$ as in [51]), and all the experiments were performed on a PC with an Intel i7-7700 CPU and 32 GB RAM.

We report the inpainting results of all the methods on the lenna and pepper images with 50% random missing pixels, as shown in Figure 1 and Figure 2. The results show that both our methods produced significantly better PSNR results than the other methods. As analyzed in [22,29], our quasi-norm formulations required significantly fewer observations than traditional nuclear norm solvers (e.g., [50]), and also led to scalable optimization problems. In particular, the resulting Schatten quasi-norm formulations may be Lipschitz, while the original Schatten quasi-norm minimization is non-Lipschitz and generally NP-hard [38].

Table 1. Comparison of running time of the methods (in seconds).

	IRNN [49]	WNNM [48]	BN	FN
lenna	2381.04	389.53	7.06	5.27
pepper	2257.39	382.78	7.35	5.31

shows the running time of all the methods. It is clear that both our methods were more than 50 times faster than the well-known methods, especially IRNN, which suffers from high computational costs due to performing SVD in each iteration.

5. Proofs of Main Results

In this section, we give the proofs for some theorems and corollaries. We first introduce several key lemmas, such as Jensen’s inequality, Hölder’s inequality, and Young’s inequality, which are used throughout our proofs.

Lemma 1 (Jensen’s inequality).

Assume that the function $g(·):{\mathbb{R}}^{+}\to {\mathbb{R}}^{+}$ is a continuous concave function on $[0,+\infty )$. For all $t_i\ge 0$ satisfying ${\sum }_i{t}_i=1$, and any $x_i\in {\mathbb{R}}^{+}$ for $i=1,\dots ,n$, then

$$g\left(\sum _{i=1}^n{t}_i{x}_i\right)\ge \sum _{i=1}^n{t}_{i}g\left(x_i\right).$$

(15)

Lemma 2 (Hölder’s inequality).

For any $p,q>1$ satisfying $1/p+1/q=1$, then for any $x_i$ and $y_i$, $i=1,\dots ,n$,

$$\sum _{i=1}^n\left|x_i{y}_i\right|\le {\left(\sum _{i=1}^n{\left|x_i\right|}^p\right)}^{1/p}{\left(\sum _{i=1}^n{\left|y_i\right|}^q\right)}^{1/q}$$

(16)

with equality iff there is a constant $c\ne 0$ such that each $x_i^p=c{y}_i^q$.

Lemma 3 (Young’s inequality).

Let $a,b\ge 0$ and $1<p,q<\infty$ be such that $1/p+1/q=1$. Then

$$\frac{a^p}{p}+\frac{b^q}{q}\ge ab$$

(17)

with equality iff $a^p=b^q$.

5.1. Proof of Theorem 1

Before giving a complete proof for Theorem 1, we first present and prove the following lemma.

Lemma 4.

Suppose that $Z\in {\mathbb{R}}^{m\times n}$ is a matrix of rank $r\le min(m,n)$, and we denote its thin SVD by $Z=L_Z{\Sigma }_Z{R}_Z^T$, where $L_Z\in {\mathbb{R}}^{m\times r}$, $R_Z\in {\mathbb{R}}^{n\times r}$, and ${\Sigma }_Z\in {\mathbb{R}}^{r\times r}$. For any $A\in {\mathbb{R}}^{r\times r}$ satisfying $A{A}^T=A^{T}A=I_{r\times r}$, and given $p(0<p\le 1)$, then ${\left(A{\Sigma }_Z{A}^T\right)}_{k,k}\ge 0$ for all $k=1,\dots ,r$, and

$$\mathrm{T}{\mathrm{r}}^p\left(A{\Sigma }_Z{A}^T\right)\ge \mathrm{T}{\mathrm{r}}^p\left({\Sigma }_Z\right)={\parallel Z\parallel }_{S_p}^p,$$

where $\mathrm{T}{\mathrm{r}}^p\left(B\right)={\sum }_i{B}_{ii}^p$.

Proof. 

For any $k\in \{1,\dots ,r\}$, we have ${\left(A{\Sigma }_Z{A}^T\right)}_{k,k}={\sum }_i{a}_{ki}^2{\sigma }_i\ge 0$, where ${\sigma }_i\ge 0$ is the i-th singular value of Z. Then

$$\mathrm{T}{\mathrm{r}}^p\left(A{\Sigma }_Z{A}^T\right)=\sum _k{\left(\sum _i{a}_{ki}^2{\sigma }_i\right)}^p.$$

(18)

Recall that $g\left(x\right)=x^p$ with $0<p<1$ is a concave function on ${\mathbb{R}}^{+}$. By Jensen’s inequality [52], as stated in Lemma 1, and ${\sum }_i{a}_{ki}^2=1$ for any $k\in \{1,\dots ,r\}$, we have

$${\left(\sum _i{a}_{ki}^2{\sigma }_i\right)}^p\ge \sum _i{a}_{ki}^2{\sigma }_i^p.$$

Using the above inequality and ${\sum }_k{a}_{ki}^2=1$ for any $i\in \{1,\dots ,r\}$, (18) can be rewritten as

$$\begin{array}{cc}\hfill \mathrm{T}{\mathrm{r}}^p\left(A{\Sigma }_Z{A}^T\right)=\sum _k{\left(\sum _i{a}_{ki}^2{\sigma }_i\right)}^p& \ge \sum _k\sum _i{a}_{ki}^2{\sigma }_i^p\hfill \\ \hfill & =\sum _i{\sigma }_i^p=\mathrm{T}{\mathrm{r}}^p\left({\Sigma }_Z\right)={\parallel Z\parallel }_{S_p}^p.\hfill \end{array}$$

(19)

In addition, when $g\left(x\right)=x$ (i.e., $p=1$), we obtain

$${\left(\sum _i{a}_{ki}^2{\sigma }_i\right)}^p=\sum _i{a}_{ki}^2{\sigma }_i,$$

which means that the inequality (19) is still satisfied. □

Proof of Theorem 1.

Let $U=L_U{\Sigma }_U{R}_U^T$ and $V=L_V{\Sigma }_V{R}_V^T$ be the thin SVDs of U and V, respectively, where $L_U\in {\mathbb{R}}^{m\times d}$, $L_V\in {\mathbb{R}}^{n\times d}$, and $R_U,{\Sigma }_U,R_V,{\Sigma }_V\in {\mathbb{R}}^{d\times d}$. $X=L_X{\Sigma }_X{R}_X^T$, where the columns of $L_X\in {\mathbb{R}}^{m\times d}$ and $R_X\in {\mathbb{R}}^{n\times d}$ are the left and right singular vectors associated with the top d singular values of X with rank at most r$(r\le d)$, and ${\Sigma }_X=\mathrm{diag}\left([{\sigma }_1\left(X\right),\cdots ,{\sigma }_r\left(X\right),0,\cdots ,0]\right)\in {\mathbb{R}}^{d\times d}$.

Recall that $X=U{V}^T$ (i.e., $L_X{\Sigma }_X{R}_X^T=L_U{\Sigma }_U{R}_U^T{R}_V{\Sigma }_V{L}_V^T$), then $\exists O_1,{\widehat{O}}_1\in {\mathbb{R}}^{d\times d}$ satisfy $L_X=L_U{O}_1$ and $L_U=L_X{\widehat{O}}_1$, which implies that $O_1=L_U^T{L}_X$ and ${\widehat{O}}_1=L_X^T{L}_U$. Thus, $O_1={\widehat{O}}_1^T$. Since $L_X=L_U{O}_1=L_X{\widehat{O}}_1{O}_1$, we have ${\widehat{O}}_1{O}_1=O_1^T{O}_1=I_d$. Similarly, we have $O_1{\widehat{O}}_1=O_1{O}_1^T=I_d$. In addition, $\exists O_2\in {\mathbb{R}}^{d\times d}$ satisfies $R_X=L_V{O}_2$ with $O_2{O}_2^T=O_2^T{O}_2=I_d$. Let $O_3=O_2{O}_1^T\in {\mathbb{R}}^{d\times d}$, then we have $O_3{O}_3^T=O_3^T{O}_3=I_d$, that is, ${\sum }_i{\left(O_3\right)}_{ij}^2={\sum }_j{\left(O_3\right)}_{ij}^2=1$ for $\forall i,j\in \{1,2,\dots ,d\}$, where $a_{i,j}$ denotes the element in the i-th row and the j-th column of the matrix A. In addition, let $O_4=R_U^T{R}_V$, we have ${\sum }_i{\left(O_4\right)}_{ij}^2\le 1$ and ${\sum }_j{\left(O_4\right)}_{ij}^2\le 1$ for $\forall i,j\in \{1,2,\dots ,d\}$.

According to the above analysis, we have $O_2{\Sigma }_X{O}_2^T=O_2{O}_1^T{\Sigma }_U{O}_4{\Sigma }_V=O_3{\Sigma }_U{O}_4{\Sigma }_V$. Let ${\varrho }_i$ and ${\tau }_j$ denote the i-th and j-th diagonal elements of ${\Sigma }_U$ and ${\Sigma }_V$, respectively. In the following, we consider the two cases of $p_1$ and $p_2$, that is, at least one of $p_1$ and $p_2$ must be no less than 1, or both of them are smaller than 1. It is clear that for any $1/2\le p\le 1$ and $p_1,p_2>0$ satisfying $1/p_1+1/p_2=1/p$, at least one of $p_1$ and $p_2$ must be no less than 1. On the other hand, only if $0<p<1/2$, there exist $0<p_1<1$ and $0<p_2<1$ such that $1/p_1+1/p_2=1/p$, that is, both of them are smaller than 1.

Case 1. For any $0<p\le 1$, there exist $p_1>0$ and $p_2>0$, at least one of which is no less than 1, such that $1/p_1+1/p_2=1/p$. Without loss of generality, we assume that $p_2\ge 1$. Here, we set $k_1=p_1/p$ and $k_2=p_2/p$. Clearly, we can know that $k_1,k_2>1$ and $1/k_1+1/k_2=1$. From Lemma 4, we have

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}\le & {\left(\mathrm{T}{\mathrm{r}}^p\left(O_2{\Sigma }_X{O}_2^T\right)\right)}^{1/p}={\left(\mathrm{T}{\mathrm{r}}^p\left(O_2{O}_1^T{\Sigma }_U{O}_4{\Sigma }_V\right)\right)}^{1/p}={\left(\mathrm{T}{\mathrm{r}}^p\left(O_3{\Sigma }_U{O}_4{\Sigma }_V\right)\right)}^{1/p}\hfill \\ \hfill =& {\left(\sum _{i=1}^d{\left[\sum _{j=1}^d{\tau }_j{\left(O_3\right)}_{ij}{\left(O_4\right)}_{ji}{\varrho }_i\right]}^p\right)}^{1/p}={\left(\sum _{i=1}^d{\varrho }_i^p{\left(\sum _{j=1}^d{\tau }_j{\left(O_3\right)}_{ij}{\left(O_4\right)}_{ji}\right)}^p\right)}^{1/p}\hfill \\ \hfill {}^a\le & {\left({\left[\sum _{i=1}^d{\left({\varrho }_i^p\right)}^{k_1}\right]}^{1/k_1}{\left[\sum _{i=1}^d{\left(\sum _{j=1}^d{\tau }_j{\left(O_3\right)}_{ij}{\left(O_4\right)}_{ji}\right)}^{p\times k_2}\right]}^{1/k_2}\right)}^{1/p}\hfill \\ \hfill =& {\left(\sum _{i=1}^d{\varrho }_i^{p_1}\right)}^{1/p_1}{\left[\sum _{i=1}^d{\left(\sum _{j=1}^d{\tau }_j{\left(O_3\right)}_{ij}{\left(O_4\right)}_{ji}\right)}^{p_2}\right]}^{1/p_2}\hfill \\ \hfill {}^b\le & {\left(\sum _{i=1}^d{\varrho }_i^{p_1}\right)}^{1/p_1}{\left[\sum _{i=1}^d{\left(\sum _{j=1}^d{\tau }_j\frac{{\left(O_3\right)}_{ij}^2+{\left(O_4\right)}_{ji}^2}{2}\right)}^{p_2}\right]}^{1/p_2}\hfill \\ \hfill {}^c\le & {\left(\sum _{i=1}^d{\varrho }_i^{p_1}\right)}^{1/p_1}{\left(\sum _{j=1}^d{\tau }_j^{p_2}\right)}^{1/p_2},\hfill \end{array}$$

where the inequality ${}^a\le$ holds due to the Hölder’s inequality [52], as stated in Lemma 2. The inequality ${}^b\le$ follows from the basic inequality $xy\le \frac{x^2+y^2}{2}$ for any real numbers x and y, and the inequality ${}^c\le$ relies on the facts that ${\sum }_i{\left(O_3\right)}_{ij}^2=1$ and ${\sum }_i{\left(O_4\right)}_{ji}^2\le 1$, and we apply Jensen’s inequality (see Lemma 1) for the convex function $h\left(x\right)=x^{p_2}$ with $p_2\ge 1$.

For any matrices $U\in {\mathbb{R}}^{m\times d}$ and $V\in {\mathbb{R}}^{n\times d}$ satisfying $X=U{V}^T$, we have

$${\parallel X\parallel }_{S_p}\le {\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}.$$

(20)

On the other hand, let $U_{\star }=L_X{\Sigma }_X^{p/p_1}$ and $V_{\star }=R_X{\Sigma }_X^{p/p_2}$, where ${\Sigma }_X^p$ is entry-wise power to p, then we obtain

$$X=U_{\star }{V}_{\star }^T,\parallel U_{\star }{\parallel }_{S_{p_1}}^{p_1}=\parallel V_{\star }{\parallel }_{S_{p_2}}^{p_2}={\parallel X\parallel }_{S_p}^p\mathrm{with}1/p=1/p_1+1/p_2,$$

and

$${\parallel X\parallel }_{S_p}={\left(\mathrm{T}{\mathrm{r}}^p\left({\Sigma }_X\right)\right)}^{1/p}=\parallel U_{\star }{\parallel }_{S_{p_1}}{\parallel V_{\star }\parallel }_{S_{p_2}}.$$

Therefore, under the constraint $X=U{V}^T$, we have

$${\parallel X\parallel }_{S_p}=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}.$$

Case 2. For any $0<p<1/2$, there exist $0<{\widehat{p}}_1<1$ and $0<{\widehat{p}}_2<1$ such that $1/{\widehat{p}}_1+1/{\widehat{p}}_2=1/p$. Next, we prove that the result of Theorem 1 also holds. In fact, for any given p, there must exist $p_1>0$ and $p_2\ge 1$ such that $1/p_1+1/p_2=1/p$ and $1/p_1=1/{\widehat{p}}_1+1/q$ with $q\ge 1$. Clearly, we can know that $1/{\widehat{p}}_1<1/p_1$. Let $U^{\ast }=L_X{\Sigma }_X^{p/p_1}$, $V^{\ast }=R_X{\Sigma }_X^{p/p_2}$, $U_1^{\ast }=L_X{\Sigma }_X^{p/{\widehat{p}}_1}$ and $V_1^{\ast }=R_X{\Sigma }_X^{p/{\widehat{p}}_2}$, then we have $X=U^{\ast }{\left(V^{\ast }\right)}^T=U_1^{\ast }{\left(V_1^{\ast }\right)}^T$, which implies that

$${\parallel X\parallel }_{S_p}=\parallel U^{\ast }{\parallel }_{S_{p_1}}\parallel V^{\ast }{\parallel }_{S_{p_2}}=\parallel U_1^{\ast }{\parallel }_{S_{{\widehat{p}}_1}}{\parallel V_1^{\ast }\parallel }_{S_{{\widehat{p}}_1}}.$$

(21)

Since $1/p=1/p_1+1/p_2=1/{\widehat{p}}_1+1/{\widehat{p}}_2$ and $1/p_1=1/{\widehat{p}}_1+1/q$, then $1/{\widehat{p}}_2=1/q+1/p_2$. Consider any factor matrices U and V satisfying $X=U{V}^T$, $V=L_V{\Sigma }_V{R}_V^T$ is the thin SVD of V. Let $U_1=U{U}_2^T$ and $V_1=L_V{\Sigma }_V^{{\widehat{p}}_2/p_2}$, where $U_2^T=R_V{\Sigma }_V^{{\widehat{p}}_2/q}$, and thus it is not difficult to verify that

$$\begin{array}{c}\hfill V=V_1{U}_2,X=U_1{V}_1^T{,\parallel V\parallel }_{S_{{\widehat{p}}_2}}=\parallel U_2{\parallel }_{S_q}\parallel V_1{\parallel }_{S_{p_2}},\parallel U_1{\parallel }_{S_{p_1}}\le {\parallel U\parallel }_{S_{{\widehat{p}}_1}}{\parallel U_2\parallel }_{S_q},\end{array}$$

(22)

where the above inequality follows from (20) with $q\ge 1$. Combining (21) and (22) and for any U and V satisfying $X=U{V}^T$, we have

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}=\parallel U^{\ast }{\parallel }_{S_{p_1}}{\parallel V^{\ast }\parallel }_{S_{p_2}}& \le \parallel U_1{\parallel }_{S_{p_1}}{\parallel V_1\parallel }_{S_{p_2}}\hfill \\ \hfill & \le {\parallel U\parallel }_{S_{{\widehat{p}}_1}}\parallel U_2{\parallel }_{S_q}\parallel V_1{\parallel }_{S_{p_2}}={\parallel U\parallel }_{S_{{\widehat{p}}_1}}{\parallel V\parallel }_{S_{{\widehat{p}}_2}},\hfill \end{array}$$

(23)

where the first inequality follows from (20). Recall that

$${\parallel X\parallel }_{S_p}=\parallel U_1^{\ast }{\parallel }_{S_{{\widehat{p}}_1}}{\parallel V_1^{\ast }\parallel }_{S_{{\widehat{p}}_2}}.$$

(24)

Therefore, for any $0<{\widehat{p}}_1<1$ and $0<{\widehat{p}}_2<1$ satisfying $1/p=1/{\widehat{p}}_1+1/{\widehat{p}}_2$, and by (23) and (24), we also have

$${\parallel X\parallel }_{S_p}=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{S_{{\widehat{p}}_1}}{\parallel V\parallel }_{S_{{\widehat{p}}_2}}.$$

In summary, for any $0<p\le 1$, $p_1>0$ and $p_2>0$ satisfying $1/p=1/p_1+1/p_2$, we have

$${\parallel X\parallel }_{S_p}=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}.$$

This completes the proof. □

5.2. Proof of Theorem 2

Proof. 

Since $p_1=p_2=2p>0$, $1/p_1+1/p_2=1/p$, and using Theorem 1,

$${\parallel X\parallel }_{S_p}=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{S_{2p}}{\parallel V\parallel }_{S_{2p}}.$$

Due to the basic inequality $xy\le \frac{x^2+y^2}{2}$ for any real numbers x and y, we have

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}=& \underset{U,V:X=U{V}^T}{min}{\parallel U\parallel }_{S_{2p}}{\parallel V\parallel }_{S_{2p}}=\underset{U,V:X=U{V}^T}{min}{\left({\parallel U\parallel }_{S_{2p}}^p{\parallel V\parallel }_{S_{2p}}^p\right)}^{1/p}\hfill \\ \hfill \le & \underset{U,V:X=U{V}^T}{min}{\left(\frac{{\parallel U\parallel }_{S_{2p}}^{2p}+{\parallel V\parallel }_{S_{2p}}^{2p}}{2}\right)}^{1/p}.\hfill \end{array}$$

Let $U_{\star }=L_X{\Sigma }_X^{1/2}$ and $V_{\star }=R_X{\Sigma }_X^{1/2}$, where ${\Sigma }_X^{1/2}$ is entry-wise power to $1/2$. Then, we obtain

$$X=U_{\star }{V}_{\star }^T,\parallel U_{\star }{\parallel }_{S_{2p}}^{2p}=\parallel V_{\star }{\parallel }_{S_{2p}}^{2p}={\parallel X\parallel }_{S_p}^p,$$

which implies that

$${\parallel X\parallel }_{S_p}=\parallel U_{\star }{\parallel }_{S_{2p}}{\parallel V_{\star }\parallel }_{S_{2p}}={\left(\frac{\parallel U_{\star }{\parallel }_{S_{2p}}^{2p}+{\parallel V_{\star }\parallel }_{S_{2p}}^{2p}}{2}\right)}^{1/p}.$$

The theorem now follows because

$$\begin{array}{c}\hfill \underset{U,V:X=U{V}^T}{min}{\parallel U\parallel }_{S_{2p}}{\parallel V\parallel }_{S_{2p}}=\underset{U,V:X=U{V}^T}{min}{\left(\frac{{\parallel U\parallel }_{S_{2p}}^{2p}+{\parallel V\parallel }_{S_{2p}}^{2p}}{2}\right)}^{1/p}.\end{array}$$

This completes the proof. □

5.3. Proof of Theorem 3

Proof. 

For any $0<p\le 1$, $p_1>0$ and $p_2>0$ satisfying $1/p_1+1/p_2=1/p$, and using Theorem 1, we have

$${\parallel X\parallel }_{S_p}=\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}.$$

Let $k_1=(p_1+p_2)/p_2$ and $k_2=(p_1+p_2)/p_1$, and it is easy to know that $1/k_1+1/k_2=1$. Then

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}& =\underset{U,V:X=U{V}^T}{min}{\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}=\underset{U,V:X=U{V}^T}{min}{\left({\parallel U\parallel }_{S_{p_1}}^p{\parallel V\parallel }_{S_{p_2}}^p\right)}^{1/p}\hfill \\ \hfill & \le \underset{U,V:X=U{V}^T}{min}{\left(\frac{{\parallel U\parallel }_{S_{p_1}}^{p{k}_1}}{k_1}+\frac{{\parallel V\parallel }_{S_{p_2}}^{p{k}_2}}{k_2}\right)}^{1/p}\hfill \\ \hfill & =\underset{U,V:X=U{V}^T}{min}{\left(\frac{p_2{\parallel U\parallel }_{S_{p_1}}^{p_1}+p_1{\parallel V\parallel }_{S_{p_2}}^{p_2}}{p_1+p_2}\right)}^{1/p}\hfill \end{array}$$

where the above inequality follows from the well-known Young inequality and the monotone increasing property of the function $g\left(x\right)=x^{1/p}$.

Let $U_{\star }=L_X{\Sigma }_X^{p/p_1}$ and $V_{\star }=R_X{\Sigma }_X^{p/p_2}$, then $X=U_{\star }{V}_{\star }^T$ and

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}& =\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}=\parallel U_{\star }{\parallel }_{S_{p_1}}{\parallel V_{\star }\parallel }_{S_{p_2}}\hfill \\ \hfill & ={\left(\frac{p_2\parallel U_{\star }{\parallel }_{S_{p_1}}^{p_1}+p_1{\parallel V_{\star }\parallel }_{S_{p_2}}^{p_2}}{p_1+p_2}\right)}^{1/p}\hfill \end{array}$$

which implies that

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}& =\underset{U\in {\mathbb{R}}^{m\times d},V\in {\mathbb{R}}^{n\times d}:X=U{V}^T}{min}{\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}\hfill \\ \hfill & =\underset{U,V:X=U{V}^T}{min}{\left(\frac{p_2{\parallel U\parallel }_{S_{p_1}}^{p_1}+p_1{\parallel V\parallel }_{S_{p_2}}^{p_2}}{p_1+p_2}\right)}^{1/p}\hfill \\ \hfill & =\underset{U,V:X=U{V}^T}{min}{\left(\frac{{\parallel U\parallel }_{S_{p_1}}^{p_1}/p_1+{\parallel V\parallel }_{S_{p_2}}^{p_2}/p_2}{1/p}\right)}^{1/p}.\hfill \end{array}$$

(25)

This completes the proof. □

5.4. Proof of Theorem 4

Proof. 

Let $U\in {\mathbb{R}}^{m\times d}$ and $\widehat{V}\in {\mathbb{R}}^{n\times d}$ be any factor matrices such that $X=U{\widehat{V}}^T$, and ${\widehat{p}}_1=p_1>0$ and ${\widehat{p}}_2=p_2{p}_3/(p_2+p_3)>0$, which means that $1/{\widehat{p}}_1+1/{\widehat{p}}_2=1/p$. According to Theorem 1, we obtain

$${\parallel X\parallel }_{S_p}=\underset{U\in {\mathbb{R}}^{m\times d},\widehat{V}\in {\mathbb{R}}^{n\times d}:X=U{\widehat{V}}^T}{min}{\parallel U\parallel }_{S_{{\widehat{p}}_1}}{\parallel \widehat{V}\parallel }_{S_{{\widehat{p}}_2}}.$$

(26)

Let $V\in {\mathbb{R}}^{d\times d}$ and $W\in {\mathbb{R}}^{n\times d}$ be factor matrices of $\widehat{V}$ (i.e., $V{W}^T={\widehat{V}}^T$). Since ${\widehat{p}}_2=p_2{p}_3/(p_2+p_3)$, then $1/{\widehat{p}}_2=1/p_2+1/p_3$ and

$$\parallel \widehat{V}{\parallel }_{S_{{\widehat{p}}_2}}=\underset{V\in {\mathbb{R}}^{d\times d},W\in {\mathbb{R}}^{n\times d}:\widehat{V}={\left(V{W}^T\right)}^T}{min}{\parallel V\parallel }_{S_{p_2}}{\parallel W\parallel }_{S_{p_3}}.$$

(27)

Combining (26) and (27), we obtain

$${\parallel X\parallel }_{S_p}=\underset{U,V,W:X=UV{W}^T}{min}{\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}{\parallel W\parallel }_{S_{p_3}}.$$

Using the above result, we have

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}=& \underset{U,V,W:X=UV{W}^T}{min}{\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}{\parallel W\parallel }_{S_{p_3}}\hfill \\ \hfill =& \underset{U,V,W:X=UV{W}^T}{min}{\left({\parallel U\parallel }_{S_{p_1}}^p{\parallel V\parallel }_{S_{p_2}}^p{\parallel W\parallel }_{S_{p_3}}^p\right)}^{1/p}\hfill \\ \hfill \le & \underset{U,V,W:X=UV{W}^T}{min}{\left(\frac{p_2{p}_3{\parallel U\parallel }_{S_{p_1}}^{p_1}+p_1{p}_3{\parallel V\parallel }_{S_{p_2}}^{p_2}+p_1{p}_2{\parallel W\parallel }_{S_{p_3}}^{p_3}}{p_2{p}_3+p_1{p}_3+p_1{p}_2}\right)}^{1/p},\hfill \end{array}$$

where the above inequality follows from the well-known Young inequality.

Let $U_{\star }=L_X{\Sigma }_X^{p/p_1}$, $V_{\star }={\Sigma }_X^{p/p_2}$, and $W_{\star }=R_X{\Sigma }_X^{p/p_3}$. It is easy to verify that $X=U_{\star }{V}_{\star }{W}_{\star }^T$. Then, we have

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}=& \underset{U,V,W:X=UV{W}^T}{min}{\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}{\parallel W\parallel }_{S_{p_3}}=\parallel U_{\star }{\parallel }_{S_{p_1}}\parallel V_{\star }{\parallel }_{S_{p_2}}{\parallel W_{\star }\parallel }_{S_{p_3}}\hfill \\ \hfill =& {\left(\frac{p_2{p}_3\parallel U_{\star }{\parallel }_{S_{p_1}}^{p_1}+p_1{p}_3\parallel V_{\star }{\parallel }_{S_{p_2}}^{p_2}+p_1{p}_2{\parallel W_{\star }\parallel }_{S_{p_3}}^{p_3}}{p_2{p}_3+p_1{p}_3+p_1{p}_2}\right)}^{1/p}.\hfill \end{array}$$

Therefore, we have

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}=& \underset{U,V,W:X=UV{W}^T}{min}{\parallel U\parallel }_{S_{p_1}}{\parallel V\parallel }_{S_{p_2}}{\parallel W\parallel }_{S_{p_3}}\hfill \\ \hfill =& \underset{U,V,W:X=UV{W}^T}{min}{\left(\frac{p_2{p}_3{\parallel U\parallel }_{S_{p_1}}^{p_1}+p_1{p}_3{\parallel V\parallel }_{S_{p_2}}^{p_2}+p_1{p}_2{\parallel W\parallel }_{S_{p_3}}^{p_3}}{p_2{p}_3+p_1{p}_3+p_1{p}_2}\right)}^{1/p}\hfill \\ \hfill =& \underset{U,V,W:X=UV{W}^T}{min}{\left(\frac{{\parallel U\parallel }_{S_{p_1}}^{p_1}/p_1+{\parallel V\parallel }_{S_{p_2}}^{p_2}/p_2+{\parallel W\parallel }_{S_{p_3}}^{p_3}/p_3}{1/p}\right)}^{1/p}.\hfill \end{array}$$

This completes the proof. □

5.5. Proof of Corollary 2

Proof. 

Since $p_1=p_2=p_3=3p>0$ and $1/p_1+1/p_2+1/p_3=1/p$, and using Theorem 4, we have

$${\parallel X\parallel }_{S_p}=\underset{U,V,W:X=UV{W}^T}{min}{\parallel U\parallel }_{S_{3p}}{\parallel V\parallel }_{S_{3p}}{\parallel W\parallel }_{S_{3p}}.$$

From the basic inequality $xyz\le \frac{x^3+y^3+z^3}{3}$ for arbitrary positive numbers x, y, and z, we obtain

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}=& \underset{U,V,W:X=UV{W}^T}{min}{\parallel U\parallel }_{S_{3p}}{\parallel V\parallel }_{S_{3p}}{\parallel W\parallel }_{S_{3p}}\hfill \\ \hfill =& \underset{U,V,W:X=UV{W}^T}{min}{\left({\parallel U\parallel }_{S_{3p}}^p{\parallel V\parallel }_{S_{3p}}^p{\parallel W\parallel }_{S_{3p}}^p\right)}^{1/p}\hfill \\ \hfill \le & \underset{U,V,W:X=UV{W}^T}{min}{\left(\frac{{\parallel U\parallel }_{S_{3p}}^{3p}+{\parallel V\parallel }_{S_{3p}}^{3p}+{\parallel W\parallel }_{S_{3p}}^{3p}}{3}\right)}^{1/p}.\hfill \end{array}$$

Let $U_{\star }=L_X{\Sigma }_X^{1/3}$, $V_{\star }={\Sigma }_X^{1/3}$, and $W_{\star }=R_X{\Sigma }_X^{1/3}$, where ${\Sigma }_X^{1/3}$ is entry-wise power to $1/3$, then we have

$$X=U_{\star }{V}_{\star }{W}_{\star }^T,\parallel U_{\star }{\parallel }_{S_{3p}}^{3p}=\parallel V_{\star }{\parallel }_{S_{3p}}^{3p}=\parallel W_{\star }{\parallel }_{S_{3p}}^{3p}={\parallel X\parallel }_{S_p}^p,$$

which implies that

$$\begin{array}{cc}\hfill {\parallel X\parallel }_{S_p}=& \parallel U_{\star }{\parallel }_{S_{3p}}\parallel V_{\star }{\parallel }_{S_{3p}}{\parallel W_{\star }\parallel }_{S_{3p}}\hfill \\ \hfill =& {\left(\frac{\parallel U_{\star }{\parallel }_{S_{3p}}^{3p}+\parallel V_{\star }{\parallel }_{S_{3p}}^{3p}+{\parallel W_{\star }\parallel }_{S_{3p}}^{3p}}{3}\right)}^{1/p}.\hfill \end{array}$$

The theorem now follows because

$$\begin{array}{cc}\hfill & \underset{U,V,W:X=UV{W}^T}{min}{\parallel U\parallel }_{S_{3p}}{\parallel V\parallel }_{S_{3p}}{\parallel W\parallel }_{S_{3p}}\hfill \\ \hfill =& \underset{U,V,W:X=UV{W}^T}{min}{\left(\frac{{\parallel U\parallel }_{S_{3p}}^{3p}+{\parallel V\parallel }_{S_{3p}}^{3p}+{\parallel W\parallel }_{S_{3p}}^{3p}}{3}\right)}^{1/p}.\hfill \end{array}$$

This completes the proof. □

6. Conclusions

Generally, the Schatten quasi-norm minimization problem is non-convex, non-smooth, and even non-Lipschitz, and thus most existing algorithms are too slow or even impractical for large-scale matrix recovery and completion problems. Therefore, it is very important to know how to transform such challenging problems into simpler ones. In this paper, we first presented and rigorously proved that for any p, $p_1$, $p_2>0$ satisfying $1/p=1/p_1+1/p_2$, the Schatten p-quasi-norm of any matrix is equivalent to the minimization of the product (or weighted sum) of the Schatten $p_1$-(quasi-)norm and Schatten $p_2$-(quasi-)norm of two much smaller factor matrices. 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 (i.e., Property 1). That is, the Schatten quasi-norm minimization problem with $p>1/2$ can be transformed into a simpler one only involving the smooth norms of smaller factor matrices, which can naturally lead to simpler and more efficient algorithms (e.g., [12,22,29,30]).

We further extended the equivalence formulation 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 $(\lfloor 1/p\rfloor +1)p$-norms of $\lfloor 1/p\rfloor +1$ factor matrices. In other words, for any $0<p<1$, the Schatten quasi-norm minimization problem can be transformed into an optimization problem only involving the smooth norms of multiple factor matrices. Finally, we provided some representative examples for two and three factor matrices. It is clear that the bi-nuclear and Frobenius/nuclear quasi-norms in our previous work [22] and the tri-nuclear quasi-norm in our previous work [29] are three important special cases. Our future work is the theoretical analysis of the properties of the proposed unified Schatten p-norm formulations compared to the nuclear norm and the Schatten quasi-norm as in [53,54] (e.g., how many observations are sufficient for our models to reliably recover low-rank matrices).