A Perturbation Analysis of Low-Rank Matrix Recovery by Schatten p-Minimization ()
1. Introduction
Low-rank matrix recovery (LMR) is a fast-growing field nowadays, attracting much attention in numerous applications such as quantum state tomography scanners [1] , deep learning [2] , nonlinear system identification [3] , computer visualization [4] , and medical imaging [5] . The mathematical expression of the low-rank matrix recovery issue is described as
(1)
where
is an unknown low-rank matrix or approximate low-rank matrix, which need be recovered and
is a known observation vector,
is a given measurement operator or linear mapping which is defined by the following formula
(2)
where
are named the measurement matrices,
is the transpose matrix of X and
is the trace function. The main goal of LMR is to recover the low-rank matrix X on the basis of observation vector b and operator
.
Actually, the linear measurement b is affected by the noisy vector y. The noisy LMR model is shown by
, (3)
is an observed measurement disturbed by the noise vector y, y is an additive noise that does not depend on X.
Moreover, more LMR models may involve casein which the observed vector b is perturbed noise vector , meanwhile, the linear mapping
is hampered by Φ, i.e.,
is replaced by
to bring about multiplicative noise Φ(X) associated with X. In a large number of applications of complete separation problems such as remote sensing [6] , source separation [7] , and telecommunication [8] , complete perturbation problems usually arise. In order to require the optimal solution from this fully perturbed problems, a common approach is to solve a class of nuclear norm minimization issues (NNM) as described below:
, (4)
where
represents the overall noise,
is the trace norm of the matrix X, namely the sum of its singular values. While
and
is diagonal matrix, issue (4) relegates into a compressed sensing issue
, (5)
here
is
the norm of the vector
, in a word, the sum of the absolute values of the elements of
.
Chartrand’s study [9] revealed that nonconvex variants of (5) can produce accurate reconstruction with fewer measurements. Specifically, the
norm minimization is substituted with the
norm minimization:
, (6)
in which
is
-quasi-norm of vector
. Even though the
-quasi-norm is not a norm, but it satisfies the triangle inequality.
Numerous studies have focused on the recovery of vector
by
minimization (
) [10] [11] [12] . Chartrand [9] conducts numerical experiments using random and non-random Fourier measurements, which acquied fewer measurements are required for accurate restoration than when p = 1. Chartrand [13] extended the result of Restricted Isometry Property (RIP) in Candès and Tao [14] to the case of
minimization. Kong and Xiu [15] explored nonconvex relaxation methods for recovering the vector x. In summary, the case of (6) where x is free of the noise and perturbation for (
) extends to the matrix, referred to as
-minimization:
. (7)
The related work [13] considers the scenario of matrix recovery with noise but without perturbation, i.e., where the linear mapping
is not interfered with by Φ. From an applied and practical perspective, it is crucial to investigate the problem of rank-r matrix recovery in the fully perturbed case.
Therefore, we present the fully perturbed model of LMR through nonconvex Schatten p-norm minimization (
):
(8)
a p-norm of matrix X, and
, its singular value
decomposition (SVD) is
,
being the ith singular value of X. This model characterizes the problem of rank-r matrix recovery in a fully perturbed scenario, with
,
,
,
,
,
, and
as parameters in the model.
Now, unlike the previous concept of restricted isometry constant, this paper follows the notion of restricted isometry property (p-RIP) given by Zhang in the article [13] , which is viewed below:
Definition 1.1 (p-RIP of the measurement mapping (or operator)
) For the measurement operator
, a positive integer r and
, the restricted p-isometry constant (p-RIC) of order r denoted by
and for any matrix
and
, which has
(9)
If
, then
meets the restricted p-isometry property of order r.
The restricted isometry property (RIP) of matrix is an essential tool for LMR theory analysis. For the accurate LMR (i.e.,
,
in (1)) or a noisy/partly perturbed LMR (i.e.,
in (7)), there are some sufficient conditions based on RIP, which include
, when
and
[16] ,
[17] .
Moreover, another crucial tool for analyzing low-rank matrix recovery is the null space property (NSP) of the linear mapping
. Gao and Peng et al. [18] extended the general null space property to obtain the sparse vector p-null space property (p-NSP). Furthermore, we further extend sparse vector x recovery to the low-rank matrix, the notion is defined like this:
Definition 1.2 (p-NSP of measurement operator
) For the measured operator
, with a constant
and
, for any matrix
and
, there exist
(10)
so the operator
fulfills the p-null space property of order r.
2. Symbols and Main Results
Before presenting the key results of this paper, some notations similar to those of the article [19] which quantize disturbances Φ and y with different upper bounds are given like such:
(11)
Here
is the Schatten p-norm of the linear mapping
and
,
is the norm of its initial image set of
consisting of nonzero matrix of order r, furthermore
(12)
,
stands for the best r-rank approximation of X whose singular values consist of the r-largest singular values of X.
Secondly, two theorems are obtained based on the matrix of restricted p-isometry property (p-RIP) (see Definition 1.1) and the p-null space property (p-NSP) (see Definition 1.2) defined in section 1. Two theorems derive sufficient conditions guaranteeing stable and accurate recovery of rank matrices, and offer recovery error upper bounds. The content of two theorems is descripted as below:
Theorem 2.1: Let there be a linear operator
,
and
. Let
and
, if the restricted p-isometry constant of the linear operator
fulfills
(13)
a general matrix X with r-rank meets
(14)
and the overall noise is
(15)
,
,
and
.
is the feasible solution of the fully perturbed Schatten p-norm minimization problem
(16)
The error estimation of X and
fulfills
(17)
where
Theorem 2.2: For a given
, supposing that the linear measured operator
fulfills the p-null space property (p-NSP) with constants
and
and conditions of (13) and (14) hold. Suppose
,
,
,
holds.
is the feasible solution to the completely perturbed Schatten p-norm minimization problem
(18)
then error estimation of X and
satisfies
(19)
where
3. Proof of Key Results
Proofs of our key results are presented in this section. To prove theorem 2.1 and theorem 2.2 such that we need the support of the following five lemmas and their proofs. We start this section with a lemma with respect to Schatten p norm.
Lemma 3.1: If
. Presume that
are matrices with
and
. Then
1)
; 2)
.
When
,
and
are the trace(or nuclear ) norm of matrix D.
Lemma 3.2: For any
, there is
(20)
Proof of the lemma 3.2 suppose
and
is the optimal solution to the problem (8), which yields
(21)
Applying the inverse triangle inequality to the above Equation (21), we get
(22)
Again, by Lemma 3.1 and inequality (22), we obtain
(23)
Combining (21), (22), (23) and integrating their shifted terms, it is easy to show that
(24)
which finishes the proof of the above lemma.
Lemma 3.3: For any vector
, there is
(25)
Proof of the lemma 3.3 By definition of the
norm, there is
, and exploiting the Holder’s inequality, we suffice to obtain
Therefore, the lemma 3.3 is proved.
Next, the restricted isometry constant RIC
and the relative disturbance upper bound
of the measured operator
which does not have perturbations are already present, and Lemma 3.4 gives p-RIP condition of the perturbed measurement operator
and
.
Lemma 3.4: (The perturbed measurement operator
of the P-RIP) Assume that the r-order RIC of the
is denoted as
, and the upper bound on the relative perturbation corresponding to the operator Φ is
and fix constant
, then
of the RIC
,
as the smallest and positive number that obeys
(26)
for any matrices X which are r-rank.
Proof of the lemma 3.4 inspired by [20] , first we define
and
are the smallest positive or zero numbers that satisfy
(27)
for any matrix X with rank at most r.
Using the triangle inequality, (9) and (11), we acquire
(28)
Because of the concept of
, it means that
, (29)
by applying the above inequality (29), we obtain a minimum upper bound
(30)
Similarly, taking advantage of the inverse triangle inequality, combined with the concept of RIC and (11) yields
. (31)
Observe carefully that
and
. Based on the given
and
, we choose
the smallest nonnegative constant that makes (27) symmetric. Clearly, the true RIC of
satisfies
. The proof of Lemma 3.4 is completed.
Finally, the following lemma 3.5 clarifies that the perturbed measurement operator
can also comply with p-NSP, provided that the constants s and τ satisfy specific conditions and the measurement operator
satisfies p-NSP.
Lemma 3.5: For the given
, the measured operator
satisfies the p-null space property with a constant
and a constant
, which satisfies the condition of (10) for any
, and fix two constants
and
. Then two constants
and
, and the perturbed measurement operator
satisfies p-NSP.
Proof of the lemma 3.5 Utilizing (11) and the inequality, there are
(32)
Since
satisfies the p-null space property and
holds, we achieve
(33)
Then we collapse the inequality (33) to conclude that
Let
and
, basing the fact that
to make
, we need to solve the following inequality
, which imitates
.
In view of
in (11), and it is also known that
to make
, we must solve
after sorting out the above inequality, we obtain
Combining the above, while two constants
and
, we are able to come true
and
, hence the measurement operator
obeys p-RNSP. In summary, we prove the Lemma 3.5.
After the previous preparations, we now prove two theorems. The upper bound estimation of the error of a real matrix X to be recovered with the optimal solution
of problem (8) is derived from the restricted isometry property, i.e., theorem 2.1.
Proof of the theorem 2.1 Let
, X be the real matrix that we expect to recover,
be the optimal solution to the problem (8). We apply the block decomposition of the SVD of the matrix Z given by
where
with
and
,
,
it is clear that
, and
and
.
Let SVD of
be described by
where matrices
are orthogonal,
denotes a vector consisting of the singular values of
and
. We divide
into the sum of the vectors
,
,
, each
has sparsity 2r (except possibly
). Then,
is the portion of
that corresponds to the
largest singular values,
is the part that corresponds to the next k largest singular values, then so forth. Obviously, for all
,
and
, and
.
The following results can be derived from [17]
(34)
(35)
According to (34), we get
(36)
Applying Lemma 3.2 to (36), we can have
(37)
Since
and the triangular inequality, it suffices to
Therefore, by combining the above equation with lemma 3.3, we have
(38)
Moreover, by Lemma 3.4 and (37), we get
(39)
in that case
(40)
From (40) and Lemma 3.2, we have that
(41)
which finishes the proof of theorem 2.1.
When constants
and
, setting
, a new RIP condition that can robustly and accurately recover low-rank matrices is obtained i.e., (2 - 3) in Theorem 2.1, and it is slightly weaker than the sufficient condition of Zhang M [16]
.
Theorem2.2 is based on this element of the NSP of matrix, and provides an error-bound estimation of the actual r-rank matrix X to be found and the optimal solution
of problem (8). Its proof steps as below:
Proof According to Lemma 3.4, while
meets the p-null space property (pNSP), there exist
(42)
Let
, it is obvious that we get that by the lemma 3.2 and (42), we
(43)
holds through the lemma 3.2 and (42). After simplifying, we further obtain
(44)
Finally, we conclude from (38), (43) and (44) that
holds for
. Meanwhile, we finish the proof of the theorem 2.2.
In brief, the above completes all proofs of the two theorems.
4. Conclusion
We primarily investigate mainly study fully perturbed problem of reconstructing a low-rank matrix through nonconvex Schatten p-norm minimization and give sufficient conditions for recovering the error along with corresponding upper bound estimations. These results show that nonconvex Schatten p-minimization provides a stable and accurate guarantee for reconstructing low-rank matrix in the existence of overall noise. The obtained results involve two implications, firstly, it suffices to guide the selection of measurement operators for low-rank matrix reconstruction, i.e., operators that satisfy weaker RIC sufficient conditions can also better promote the recovery capacity; secondly, it provides theoretical support for boundary error by taking advantage of the following two properties, respectively p-RIP and p-NSP.