# s-Goodness for Low-Rank Matrix Recovery

Authors: Lingchen Kong; Levent Tunçel; Naihua Xiu
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

Low-rank matrix recovery (LMR) is a rank minimization problem subject to linear equality
constraints, and it arises in many fields such as signal and image processing, statistics, computer vision, and
system identification and control. This class of optimization problems is generally𝒩𝒫 hard. A popular approach replaces the rank function with the nuclear norm of the matrix
variable. In this paper, we extend and characterize the concept of s-goodness for a sensing matrix in sparse signal recovery (proposed by Juditsky and Nemirovski (Math Program, 2011))
to linear transformations in LMR. Using the two characteristic s-goodness constants, γs and γ^s, of a linear transformation, we derive necessary and sufficient conditions for a linear transformation to be s-good. Moreover, we establish the equivalence of s-goodness and the null space properties. Therefore, s-goodness is a necessary and sufficient condition for exact s-rank matrix recovery via the nuclear norm minimization.


---

## Body

## 1. Introduction

Low-rank matrix recovery (LMR for short) is a rank minimization problem (RMP) with linear constraints or the affine matrix rank minimization problem which is defined as follows:
(1)minimizerank(X),subjectto𝒜X=b,
where X∈ℝm×n is the matrix variable, 𝒜:ℝm×n→ℝp is a linear transformation, and b∈ℝp. Although specific instances can often be solved by specialized algorithms, the LMR is 𝒩𝒫 hard. A popular approach for solving LMR in the systems and control community is to minimize the trace of a positive semidefinite matrix variable instead of its rank (see, e.g., [1, 2]). A generalization of this approach to nonsymmetric matrices introduced by Fazel et al. [3] is the famous convex relaxation of LMR (1), which is called nuclear norm minimization (NNM):
(2)min∥X∥*s.t.𝒜X=b,
where ∥X∥* is the nuclear norm of X, that is, the sum of its singular values. When m=n and the matrix X:=Diag(x), x∈ℝn, is diagonal, the LMR (1) reduces to sparse signal recovery (SSR), which is the so-called cardinality minimization problem (CMP):
(3)min∥x∥0s.t.Φx=b,
where ∥x∥0 denotes the number of nonzero entries in the vector x and Φ∈ℝm×n is a given sensing matrix. A well-known heuristic for SSR is the ℓ1-norm minimization relaxation (basis pursuit problem):
(4)min∥x∥1s.t.Φx=b,
where ∥x∥1 is the ℓ1-norm of x, that is, the sum of absolute values of its entries.LMR problems have many applications and they appeared in the literature of a diverse set of fields including signal and image processing, statistics, computer vision, and system identification and control. For more details, see the recent paper [4]. LMR and NNM have been the focus of some recent research in the optimization community, see; for example, [4–15]. Although there are many papers dealing with algorithms for NNM such as interior-point methods, fixed point and Bregman iterative methods, and proximal point methods, there are fewer papers dealing with the conditions that guarantee the success of the low-rank matrix recovery via NNM. For instance, following the program laid out in the work of Candès and Tao in compressed sensing (CS, see, e.g., [16–18]), Recht et al. [4] provided a certain restricted isometry property (RIP) condition on the linear transformation which guarantees that the minimum nuclear norm solution is the minimum rank solution. Recht et al. [14, 19] gave the null space property (NSP) which characterizes a particular property of the null space of the linear transformation, which is also discussed by Oymak et al. [20, 21]. Note that NSP states a necessary and sufficient condition for exactly recovering the low-rank matrix via nuclear norm minimization. Recently, Chandrasekaran et al. [22] proposed that a fixed s-rank matrix X0 can be recovered if and only if the null space of 𝒜 does not intersect the tangent cone of the nuclear norm ball at X0.In the setting of CS, there are other characterizations of the sensing matrix, under whichℓ1-norm minimization can be guaranteed to yield an optimal solution to SSR, in addition to RIP and null-space properties, see; for example, [23–26]. In particular, Juditsky and Nemirovski [24] established necessary and sufficient conditions for a Sensing matrix to be “s-good” to allow for exact ℓ1-recovery of sparse signals with s nonzero entries when no measurement noise is present. They also demonstrated that these characteristics, although difficult to evaluate, lead to verifiable sufficient conditions for exact SSR and to efficiently computable upper bounds on those s for which a given sensing matrix is s-good. Furthermore, they established instructive links between s-goodness and RIP in the CS context. One may wonder whether we can generalize the s-goodness concept to LMR and still maintain many of the nice properties as done in [24]. Here, we deal with this issue. Our approach is based on the singular value decomposition (SVD) of a matrix and the partition technique generalized from CS. In the next section, following Juditsky and Nemirovski’s terminology, we propose definitions of s-goodness and G-numbers, γs and γ^s, of a linear transformation in LMR and then we provide some basic properties of G-numbers. In Section 3, we characterize s-goodness of a linear transformation in LMR via G-numbers. We consider the connections between the s-goodness, NSP, and RIP in Section 4. We eventually obtain that δ2s<0.472⇒𝒜 satisfying NSP⇔γ^s(𝒜)<1/2⇔γs(𝒜)<1⇔𝒜 is s-good.LetW∈ℝm×n, r:=min{m,n}, and let W=UDiag(σ(W))VT be an SVD of W, where U∈ℝm×r, V∈ℝn×r, and Diag(σ(W)) is the diagonal matrix of σ(W)=(σ1(W),…,σr(W))T which is the vector of the singular values of W. Also let Ξ(W) denote the set of pairs of matrices (U,V) in the SVD of W; that is,
(5)Ξ(W):={(σ(W))VT(U,V):U∈ℝm×r,V∈ℝn×r,W=UDiag(σ(W))VT}.
For s∈{0,1,2,…,r}, we say W∈ℝm×n is an s-rank matrix to mean that the rank of W is no more than s. For an s-rank matrix W, it is convenient to take W=Um×sWsVn×sT as its SVD where Um×s∈ℝm×s, Vn×s∈ℝn×s are orthogonal matrices and Ws=Diag((σ1(W),…,σs(W))T). For a vector y∈ℝp, let ∥·∥d be the dual norm of ∥·∥ specified by ∥y∥d:=maxv{〈v,y〉:∥v∥≤1}. In particular, ∥·∥∞ is the dual norm of ∥·∥1 for a vector. Let ∥X∥ denote the spectral or the operator norm of a matrix X∈ℝm×n, that is, the largest singular value of X. In fact, ∥X∥ is the dual norm of ∥X∥*. Let ∥X∥F:=〈X,X〉=Tr(XTX) be the Frobenius norm of X, which is equal to the ℓ2-norm of the vector of its singular values. We denote by XT the transpose of X. For a linear transformation 𝒜:ℝm×n→ℝp, we denote by 𝒜*:ℝp→ℝm×n the adjoint of 𝒜.


## 2. Definitions and Basic Properties

### 2.1. Definitions

We first go over some concepts related tos-goodness of the linear transformation in LMR (RMP). These are extensions of those given for SSR (CMP) in [24].Definition 1.
Let𝒜:ℝm×n→ℝp be a linear transformation and s∈{0,1,2,…,r}. One says that 𝒜 is s-good, if for every s-rank matrix W∈ℝm×n, W is the unique optimal solution to the optimization problem
(6)minX∈ℝm×n{∥X∥*:𝒜X=𝒜W}.We denote bys*(𝒜) the largest integer s for which 𝒜 is s-good. Clearly, s*(𝒜)∈{0,1,…,r}. To characterize s-goodness we introduce two useful s-goodness constants: γs and γ^s. We call γs and γ^sG-numbers.Definition 2.
Let𝒜:ℝm×n→ℝp be a linear transformation, β∈[0,+∞] and s∈{0,1,2,…,r}. Then we have the following.
(i)G-number γs(𝒜,β) is the infimum of γ≥0 such that for every matrix X∈ℝm×n with singular value decomposition X=Um×sVn×sT (i.e., s nonzero singular values, all equal to 1), there exists a vector y∈ℝp such that
(7)∥y∥d≤β,𝒜*y=UDiag(σ(𝒜*y))VT,
where U=[Um×sUm×(r-s)], V=[Vn×sVn×(r-s)] are orthogonal matrices, and
(8)σi(𝒜*y){=1,ifσi(X)=1,∈[0,γ],ifσi(X)=0,i∈{1,2,…,r}.
If there does not exist such y for some X as above, we set γs(𝒜,β)=+∞.
(ii)G-number γ^s(𝒜,β) is the infimum of γ≥0 such that for every matrix X∈ℝm×n with s nonzero singular values, all equal to 1, there exists a vector y∈ℝp such that 𝒜*y and X share the same orthogonal row and column spaces:
(9)∥y∥d≤β,∥𝒜*y-X∥≤γ.
If there does not exist such y for some X as above, we set γs(𝒜,β)=+∞ and to be compatible with the special case given by [24] we write γs(𝒜), γ^s(𝒜) instead of γs(𝒜,+∞), γ^s(𝒜,+∞), respectively.From the above definition, we easily see that the set of values thatγ takes is closed. Thus, when γs(𝒜,β)<+∞, for every matrix X∈ℝm×n with s nonzero singular values, all equal to 1, there exists a vector y∈ℝp such that(10)∥y∥d≤β,σi(𝒜*y){=1,ifσi(X)=1,∈[0,γs(𝒜,β)],ifσi(X)=0,i∈{1,2,…,r}.Similarly, for every matrix X∈ℝm×n with s nonzero singular values, all equal to 1, there exists a vector y^∈ℝp such that 𝒜*y^ and X share the same orthogonal row and column spaces:
(11)∥y^∥d≤β,∥𝒜*y^-X∥≤γ^s(𝒜,β).
Observing that the set {𝒜*y:∥y∥d≤β} is convex, we obtain that if γs(𝒜,β)<+∞ then for every matrix X with at most s nonzero singular values and ∥X∥≤1 there exist vectors y satisfying (10) and there exist vectors y^ satisfying (11).


### 2.2. Basic Properties ofG-Numbers

In order to characterize thes-goodness of a linear transformation 𝒜, we study the basic properties of G-numbers. We begin with the result that G-numbers γs(𝒜,β) and γ^s(𝒜,β) are convex nonincreasing functions of β.Proposition 3.
For every linear transformation𝒜 and every s∈{0,1,…,r}, G-numbers γs(𝒜,β) and γ^s(𝒜,β) are convex nonincreasing functions of β∈[0,+∞].Proof.
We only need to demonstrate that the quantityγs(𝒜,β) is a convex nonincreasing function of β∈[0,+∞]. It is evident from the definition that γs(𝒜,β) is nonincreasing for given 𝒜,s. It remains to show that γs(𝒜,β) is a convex function of β. In other words, for every pair β1,β2∈[0,+∞], we need to verify that
(12)γs(𝒜,αβ1+(1-α)β2)≤αγs(𝒜,β1)+(1-α)γs(𝒜,β2),∀α∈[0,1].
The above inequality follows immediately if one of β1, β2 is +∞. Thus, we may assume β1,β2∈[0,+∞). In fact, from the argument around (10) and the definition of γs(𝒜,·), we know that for every matrix X=UDiag(σ(X))VT with s nonzero singular values, all equal to 1, there exist vectors y1,y2∈ℝp such that for k∈{1,2}(13)∥yk∥d≤βk,σi(𝒜*yk){=1,ifσi(X)=1,∈[0,γs(𝒜,βk)],ifσi(X)=0,i∈{1,2,…,r}.It is immediate from (13) that ∥αy1+(1-α)y2∥d≤αβ1+(1-α)β2. Moreover, from the above information on the singular values of 𝒜*y1, 𝒜*y2, we may set 𝒜*yk=X+Yk, k∈{1,2} such that
(14)XTYk=0,XYkT=0,rank(Yk)≤r-s,∥Yk∥≤γs(𝒜,βk).
This implies that for every α∈[0,1](15)XT[αY1+(1-α)Y2]=0,X[αY1+(1-α)Y2]T=0,
and hence rank[αY1+(1-α)Y2]≤r-s, X, and [αY1+(1-α)Y2] have orthogonal row and column spaces. Thus, noting that 𝒜*[αy1+(1-α)y2]=X+αY1+(1-α)Y2, we obtain that ∥αy1+(1-α)y2∥d≤αβ1+(1-α)β2 and
(16)σi(𝒜*(αy1+(1-α)y2))={1,ifσi(X)=1,σi(αY1+(1-α)Y2),ifσi(X)=0,
for every α∈[0,1]. Combining this with the fact
(17)∥αY1+(1-α)Y2∥≤α∥Y1∥+(1-α)∥Y2∥≤αγs(𝒜,β1)+(1-α)γs(𝒜,β2),
we obtain the desired conclusion.The following observation thatG-numbers γs(𝒜,β), γ^s(𝒜,β) are nondecreasing in s is immediate.Proposition 4.
For everys′≤s, one has γs′(𝒜,β)≤γs(𝒜,β), γ^s′(𝒜,β)≤γ^s(𝒜,β).We further investigate the relationship between theG-numbers γs(𝒜,β) and γ^s(𝒜,β).Proposition 5.
Let𝒜:ℝm×n→ℝp be a linear transformation, β∈[0,+∞], and s∈{0,1,2,…,r}. Then one has
(18)γ:=γs(𝒜,β)<1⇒γ^s(𝒜,11+γβ)=γ1+γ<12,γ^:=γ^s(𝒜,β)<12⇒γs(𝒜,11-γ^β)=γ^1-γ^<1.Proof.
Letγ:=γs(𝒜,β)<1. Then, for every matrix Z∈ℝm×n with s nonzero singular values, all equal to 1, there exists y∈ℝp, ∥y∥d≤β, such that 𝒜*y=Z+W, where ∥W∥≤γ and W and Z have orthogonal row and column spaces. For a given pair Z,y as above, take y~:=(1/(1+γ))y. Then we have ∥y~∥d≤(1/(1+γ))β and
(19)∥𝒜*y~-Z∥≤max{1-11+γ,γ1+γ}=γ1+γ,
where the first term under the maximum comes from the fact that 𝒜*y and Z agree on the subspace corresponding to the nonzero singular values of Z. Therefore, we obtain
(20)γ^s(𝒜,11+γβ)≤γ1+γ<12.
Now, we assume that γ^:=γ^s(𝒜,β)<1/2. Fix orthogonal matrices U∈ℝm×r, V∈ℝn×r. For an s-element subset J of the index set {1,2,…,r}, we define a set SJ with respect to orthogonal matrices U,V as
(21)SJ:={VTJ-x∈ℝr:∃y∈ℝp,∥y∥d≤β,𝒜*y=UDiag(x)VTwith|xi|≤γ^fori∈J-}.
In the above, J- denotes the complement of J. It is immediately seen that SJ is a closed convex set in ℝr. Moreover, we have the following
Claim  1. SJ contains the ∥·∥∞-ball of radius (1-γ^) centered at the origin in ℝr.
Proof. Note that SJ is closed and convex. Moreover, SJ is the direct sum of its projections onto the pair of subspaces
(22)LJ:={x∈ℝr:xi=0,i∈J-}anditsorthogonalcomplementLJ⊥={x∈ℝr:xi=0,i∈J}.
Let Q denote the projection of SJ onto LJ. Then, Q is closed and convex (because of the direct sum property above and the fact that SJ is closed and convex). Note that LJ can be naturally identified with ℝs, and our claim is the image Q-⊂ℝs of Q under this identification that contains the ∥·∥∞-ball Bs of radius (1-γ^) centered at the origin in ℝs. For a contradiction, suppose Bs is not contained in Q-. Then there exists v∈Bs∖Q-. Since Q- is closed and convex, by a separating hyperplane theorem, there exists a vector u∈ℝs,  ∥u∥1=1 such that
(23)uTv>uTv′foreveryv′∈Q-.
Let z∈ℝr be defined by
(24)zi:={1,i∈J,0,otherwise.
By definition of γ^=γ^s(𝒜,β), for s-rank matrix UDiag(z)VT, there exists y∈ℝp such that ∥y∥d≤β and
(25)𝒜*y=UDiag(z)VT+W,
where W and UDiag(z)VT have the same orthogonal row and column spaces, ∥𝒜*y-UDiag(z)VT∥≤γ^ and ∥σ(𝒜*y)-z∥∞≤γ^. Together with the definitions of SJ and Q-, this means that Q- contains a vector v- with |v-i-sign(ui)|≤γ^, ∀i∈{1,2,…,s}. Therefore,
(26)uTv-≥∑i=1s‍|ui|(1-γ^)=(1-γ^)∥u∥1=1-γ^.
By v∈Bs and the definition of u, we obtain
(27)1-γ^≥∥v∥∞=∥u∥1∥v∥∞≥uTv>uTv-≥1-γ^,
where the strict inequality follows from the facts that v-∈Q- and u separates v from Q-. The above string of inequalities is a contradiction, and hence the desired claim holds.
Using the above claim, we conclude that for everyJ⊆{1,2,…,r} with cardinality s, there exists an x∈SJ such that xi=(1-γ^), for all i∈J. From the definition of SJ, we obtain that there exists y∈ℝp with ∥y∥d≤(1-γ^)-1β such that
(28)𝒜*y=UDiag(σ(𝒜*y))VT,
where σi(𝒜*y)=(1-γ^)-1xi=1 if i∈J, and σi(𝒜*y)i≤(1-γ^)-1γ^ if i∈J-. Thus, we obtain that
(29)γ^s:=γ^s(𝒜,β)<12⇒γs(𝒜,11-γ^β)≤γ^1-γ^<1.
To conclude the proof, we need to prove that the inequalities we established(30)γ^s(𝒜,11+γ^β)≤γ1+γ,γs(𝒜,11-γ^β)≤γ^1+γ^
are both equations. This is straightforward by an argument similar to the one in the proof of [24, Theorem  1]. We omit it for the sake of brevity.We end this section with a simple argument which illustrates that for a given pair (𝒜,s), γs(𝒜,β)=γs(𝒜) and γ^s(𝒜,β)=γ^s(𝒜), for all β large enough.Proposition 6.
Let𝒜:ℝm×n→ℝp be a linear transformation and β∈[0,+∞]. Assume that for some ρ>0, the image of the unit ∥·∥*-ball in ℝm×n under the mapping X↦𝒜X contains the ball B={x∈ℝp:∥x∥1≤ρ}. Then for every s∈{1,2,…,r}(31)β≥1ρ,γs(𝒜)<1⇒γs(𝒜,β)=γs(𝒜),β≥1ρ,γ^s(𝒜)<12⇒γ^s(𝒜,β)=γ^s(𝒜).Proof.
Fixs∈{1,2,…,r}. We only need to show the first implication. Let γ:=γs(𝒜)<1. Then for every matrix W∈ℝm×n with its SVD W=Um×sVn×sT, there exists a vector y∈ℝp such that
(32)∥y∥d≤β,𝒜*y=UDiag(σ(𝒜*y))VT,
where U=[Um×sUm×(r-s)], V=[Vn×sVn×(r-s)] are orthogonal matrices, and
(33)σi(𝒜*y){=1,ifσi(W)=1,∈[0,γ],ifσi(W)=0,i∈{1,2,…,r}.
Clearly, ∥𝒜*y∥≤1. That is,
(34)1≥∥𝒜*y∥=maxX∈ℝm×n{〈X,𝒜*y〉:∥X∥*≤1}=maxX∈ℝm×n{〈u,y〉:u=𝒜X,∥X∥*≤1}.
From the inclusion assumption, we obtain that
(35)maxX∈ℝm×n{〈u,y〉:u=𝒜X,∥X∥*≤1}≥maxu∈ℝp{〈u,y〉:∥u∥1≤ρ}=ρ∥y∥∞=ρ∥y∥d.
Combining the above two strings of relations, we derive the desired conclusion.


## 2.1. Definitions

We first go over some concepts related tos-goodness of the linear transformation in LMR (RMP). These are extensions of those given for SSR (CMP) in [24].Definition 1.
Let𝒜:ℝm×n→ℝp be a linear transformation and s∈{0,1,2,…,r}. One says that 𝒜 is s-good, if for every s-rank matrix W∈ℝm×n, W is the unique optimal solution to the optimization problem
(6)minX∈ℝm×n{∥X∥*:𝒜X=𝒜W}.We denote bys*(𝒜) the largest integer s for which 𝒜 is s-good. Clearly, s*(𝒜)∈{0,1,…,r}. To characterize s-goodness we introduce two useful s-goodness constants: γs and γ^s. We call γs and γ^sG-numbers.Definition 2.
Let𝒜:ℝm×n→ℝp be a linear transformation, β∈[0,+∞] and s∈{0,1,2,…,r}. Then we have the following.
(i)G-number γs(𝒜,β) is the infimum of γ≥0 such that for every matrix X∈ℝm×n with singular value decomposition X=Um×sVn×sT (i.e., s nonzero singular values, all equal to 1), there exists a vector y∈ℝp such that
(7)∥y∥d≤β,𝒜*y=UDiag(σ(𝒜*y))VT,
where U=[Um×sUm×(r-s)], V=[Vn×sVn×(r-s)] are orthogonal matrices, and
(8)σi(𝒜*y){=1,ifσi(X)=1,∈[0,γ],ifσi(X)=0,i∈{1,2,…,r}.
If there does not exist such y for some X as above, we set γs(𝒜,β)=+∞.
(ii)G-number γ^s(𝒜,β) is the infimum of γ≥0 such that for every matrix X∈ℝm×n with s nonzero singular values, all equal to 1, there exists a vector y∈ℝp such that 𝒜*y and X share the same orthogonal row and column spaces:
(9)∥y∥d≤β,∥𝒜*y-X∥≤γ.
If there does not exist such y for some X as above, we set γs(𝒜,β)=+∞ and to be compatible with the special case given by [24] we write γs(𝒜), γ^s(𝒜) instead of γs(𝒜,+∞), γ^s(𝒜,+∞), respectively.From the above definition, we easily see that the set of values thatγ takes is closed. Thus, when γs(𝒜,β)<+∞, for every matrix X∈ℝm×n with s nonzero singular values, all equal to 1, there exists a vector y∈ℝp such that(10)∥y∥d≤β,σi(𝒜*y){=1,ifσi(X)=1,∈[0,γs(𝒜,β)],ifσi(X)=0,i∈{1,2,…,r}.Similarly, for every matrix X∈ℝm×n with s nonzero singular values, all equal to 1, there exists a vector y^∈ℝp such that 𝒜*y^ and X share the same orthogonal row and column spaces:
(11)∥y^∥d≤β,∥𝒜*y^-X∥≤γ^s(𝒜,β).
Observing that the set {𝒜*y:∥y∥d≤β} is convex, we obtain that if γs(𝒜,β)<+∞ then for every matrix X with at most s nonzero singular values and ∥X∥≤1 there exist vectors y satisfying (10) and there exist vectors y^ satisfying (11).


## 2.2. Basic Properties ofG-Numbers

In order to characterize thes-goodness of a linear transformation 𝒜, we study the basic properties of G-numbers. We begin with the result that G-numbers γs(𝒜,β) and γ^s(𝒜,β) are convex nonincreasing functions of β.Proposition 3.
For every linear transformation𝒜 and every s∈{0,1,…,r}, G-numbers γs(𝒜,β) and γ^s(𝒜,β) are convex nonincreasing functions of β∈[0,+∞].Proof.
We only need to demonstrate that the quantityγs(𝒜,β) is a convex nonincreasing function of β∈[0,+∞]. It is evident from the definition that γs(𝒜,β) is nonincreasing for given 𝒜,s. It remains to show that γs(𝒜,β) is a convex function of β. In other words, for every pair β1,β2∈[0,+∞], we need to verify that
(12)γs(𝒜,αβ1+(1-α)β2)≤αγs(𝒜,β1)+(1-α)γs(𝒜,β2),∀α∈[0,1].
The above inequality follows immediately if one of β1, β2 is +∞. Thus, we may assume β1,β2∈[0,+∞). In fact, from the argument around (10) and the definition of γs(𝒜,·), we know that for every matrix X=UDiag(σ(X))VT with s nonzero singular values, all equal to 1, there exist vectors y1,y2∈ℝp such that for k∈{1,2}(13)∥yk∥d≤βk,σi(𝒜*yk){=1,ifσi(X)=1,∈[0,γs(𝒜,βk)],ifσi(X)=0,i∈{1,2,…,r}.It is immediate from (13) that ∥αy1+(1-α)y2∥d≤αβ1+(1-α)β2. Moreover, from the above information on the singular values of 𝒜*y1, 𝒜*y2, we may set 𝒜*yk=X+Yk, k∈{1,2} such that
(14)XTYk=0,XYkT=0,rank(Yk)≤r-s,∥Yk∥≤γs(𝒜,βk).
This implies that for every α∈[0,1](15)XT[αY1+(1-α)Y2]=0,X[αY1+(1-α)Y2]T=0,
and hence rank[αY1+(1-α)Y2]≤r-s, X, and [αY1+(1-α)Y2] have orthogonal row and column spaces. Thus, noting that 𝒜*[αy1+(1-α)y2]=X+αY1+(1-α)Y2, we obtain that ∥αy1+(1-α)y2∥d≤αβ1+(1-α)β2 and
(16)σi(𝒜*(αy1+(1-α)y2))={1,ifσi(X)=1,σi(αY1+(1-α)Y2),ifσi(X)=0,
for every α∈[0,1]. Combining this with the fact
(17)∥αY1+(1-α)Y2∥≤α∥Y1∥+(1-α)∥Y2∥≤αγs(𝒜,β1)+(1-α)γs(𝒜,β2),
we obtain the desired conclusion.The following observation thatG-numbers γs(𝒜,β), γ^s(𝒜,β) are nondecreasing in s is immediate.Proposition 4.
For everys′≤s, one has γs′(𝒜,β)≤γs(𝒜,β), γ^s′(𝒜,β)≤γ^s(𝒜,β).We further investigate the relationship between theG-numbers γs(𝒜,β) and γ^s(𝒜,β).Proposition 5.
Let𝒜:ℝm×n→ℝp be a linear transformation, β∈[0,+∞], and s∈{0,1,2,…,r}. Then one has
(18)γ:=γs(𝒜,β)<1⇒γ^s(𝒜,11+γβ)=γ1+γ<12,γ^:=γ^s(𝒜,β)<12⇒γs(𝒜,11-γ^β)=γ^1-γ^<1.Proof.
Letγ:=γs(𝒜,β)<1. Then, for every matrix Z∈ℝm×n with s nonzero singular values, all equal to 1, there exists y∈ℝp, ∥y∥d≤β, such that 𝒜*y=Z+W, where ∥W∥≤γ and W and Z have orthogonal row and column spaces. For a given pair Z,y as above, take y~:=(1/(1+γ))y. Then we have ∥y~∥d≤(1/(1+γ))β and
(19)∥𝒜*y~-Z∥≤max{1-11+γ,γ1+γ}=γ1+γ,
where the first term under the maximum comes from the fact that 𝒜*y and Z agree on the subspace corresponding to the nonzero singular values of Z. Therefore, we obtain
(20)γ^s(𝒜,11+γβ)≤γ1+γ<12.
Now, we assume that γ^:=γ^s(𝒜,β)<1/2. Fix orthogonal matrices U∈ℝm×r, V∈ℝn×r. For an s-element subset J of the index set {1,2,…,r}, we define a set SJ with respect to orthogonal matrices U,V as
(21)SJ:={VTJ-x∈ℝr:∃y∈ℝp,∥y∥d≤β,𝒜*y=UDiag(x)VTwith|xi|≤γ^fori∈J-}.
In the above, J- denotes the complement of J. It is immediately seen that SJ is a closed convex set in ℝr. Moreover, we have the following
Claim  1. SJ contains the ∥·∥∞-ball of radius (1-γ^) centered at the origin in ℝr.
Proof. Note that SJ is closed and convex. Moreover, SJ is the direct sum of its projections onto the pair of subspaces
(22)LJ:={x∈ℝr:xi=0,i∈J-}anditsorthogonalcomplementLJ⊥={x∈ℝr:xi=0,i∈J}.
Let Q denote the projection of SJ onto LJ. Then, Q is closed and convex (because of the direct sum property above and the fact that SJ is closed and convex). Note that LJ can be naturally identified with ℝs, and our claim is the image Q-⊂ℝs of Q under this identification that contains the ∥·∥∞-ball Bs of radius (1-γ^) centered at the origin in ℝs. For a contradiction, suppose Bs is not contained in Q-. Then there exists v∈Bs∖Q-. Since Q- is closed and convex, by a separating hyperplane theorem, there exists a vector u∈ℝs,  ∥u∥1=1 such that
(23)uTv>uTv′foreveryv′∈Q-.
Let z∈ℝr be defined by
(24)zi:={1,i∈J,0,otherwise.
By definition of γ^=γ^s(𝒜,β), for s-rank matrix UDiag(z)VT, there exists y∈ℝp such that ∥y∥d≤β and
(25)𝒜*y=UDiag(z)VT+W,
where W and UDiag(z)VT have the same orthogonal row and column spaces, ∥𝒜*y-UDiag(z)VT∥≤γ^ and ∥σ(𝒜*y)-z∥∞≤γ^. Together with the definitions of SJ and Q-, this means that Q- contains a vector v- with |v-i-sign(ui)|≤γ^, ∀i∈{1,2,…,s}. Therefore,
(26)uTv-≥∑i=1s‍|ui|(1-γ^)=(1-γ^)∥u∥1=1-γ^.
By v∈Bs and the definition of u, we obtain
(27)1-γ^≥∥v∥∞=∥u∥1∥v∥∞≥uTv>uTv-≥1-γ^,
where the strict inequality follows from the facts that v-∈Q- and u separates v from Q-. The above string of inequalities is a contradiction, and hence the desired claim holds.
Using the above claim, we conclude that for everyJ⊆{1,2,…,r} with cardinality s, there exists an x∈SJ such that xi=(1-γ^), for all i∈J. From the definition of SJ, we obtain that there exists y∈ℝp with ∥y∥d≤(1-γ^)-1β such that
(28)𝒜*y=UDiag(σ(𝒜*y))VT,
where σi(𝒜*y)=(1-γ^)-1xi=1 if i∈J, and σi(𝒜*y)i≤(1-γ^)-1γ^ if i∈J-. Thus, we obtain that
(29)γ^s:=γ^s(𝒜,β)<12⇒γs(𝒜,11-γ^β)≤γ^1-γ^<1.
To conclude the proof, we need to prove that the inequalities we established(30)γ^s(𝒜,11+γ^β)≤γ1+γ,γs(𝒜,11-γ^β)≤γ^1+γ^
are both equations. This is straightforward by an argument similar to the one in the proof of [24, Theorem  1]. We omit it for the sake of brevity.We end this section with a simple argument which illustrates that for a given pair (𝒜,s), γs(𝒜,β)=γs(𝒜) and γ^s(𝒜,β)=γ^s(𝒜), for all β large enough.Proposition 6.
Let𝒜:ℝm×n→ℝp be a linear transformation and β∈[0,+∞]. Assume that for some ρ>0, the image of the unit ∥·∥*-ball in ℝm×n under the mapping X↦𝒜X contains the ball B={x∈ℝp:∥x∥1≤ρ}. Then for every s∈{1,2,…,r}(31)β≥1ρ,γs(𝒜)<1⇒γs(𝒜,β)=γs(𝒜),β≥1ρ,γ^s(𝒜)<12⇒γ^s(𝒜,β)=γ^s(𝒜).Proof.
Fixs∈{1,2,…,r}. We only need to show the first implication. Let γ:=γs(𝒜)<1. Then for every matrix W∈ℝm×n with its SVD W=Um×sVn×sT, there exists a vector y∈ℝp such that
(32)∥y∥d≤β,𝒜*y=UDiag(σ(𝒜*y))VT,
where U=[Um×sUm×(r-s)], V=[Vn×sVn×(r-s)] are orthogonal matrices, and
(33)σi(𝒜*y){=1,ifσi(W)=1,∈[0,γ],ifσi(W)=0,i∈{1,2,…,r}.
Clearly, ∥𝒜*y∥≤1. That is,
(34)1≥∥𝒜*y∥=maxX∈ℝm×n{〈X,𝒜*y〉:∥X∥*≤1}=maxX∈ℝm×n{〈u,y〉:u=𝒜X,∥X∥*≤1}.
From the inclusion assumption, we obtain that
(35)maxX∈ℝm×n{〈u,y〉:u=𝒜X,∥X∥*≤1}≥maxu∈ℝp{〈u,y〉:∥u∥1≤ρ}=ρ∥y∥∞=ρ∥y∥d.
Combining the above two strings of relations, we derive the desired conclusion.


## 3.s-Goodness and G-Numbers

We first give the following characterization result ofs-goodness of a linear transformation 𝒜 via the G-number γs(𝒜), which explains the importance of γs(𝒜) in LMR.Theorem 7.
Let𝒜:ℝm×n→ℝp be a linear transformation, and s be an integer s∈{0,1,2,…,r}. Then 𝒜 is s-good if and only if γs(𝒜)<1.Proof.
Suppose𝒜 is s-good. Let W∈ℝm×n be a matrix of rank s∈{1,2,…,r}. Without loss of generality, let W=Um×sWsVn×sT be its SVD where Um×s∈ℝm×s, Vn×s∈ℝn×s are orthogonal matrices and Ws=Diag((σ1(W),…,σs(W))T). By the definition of s-goodness of 𝒜, W is the unique solution to the optimization problem (6). Using the first-order optimality conditions, we obtain that there exists y∈ℝp such that the function fy(x)=∥X∥*-yT[𝒜X-𝒜W] attains its minimum value over X∈ℝm×n at X=W. So 0∈∂fy(W) or 𝒜*y∈∂∥W∥*. Using the fact (see, e.g., [27])
(36)∂∥W∥*={Um×sVn×sT+M:WandMhaveorthogonalrowandcolumnspaces,and∥M∥≤1Vn×sT},
it follows that there exist matrices Um×(r-s), Vn×(r-s) such that 𝒜*y=UDiag(σi(𝒜*y))VT where U=[Um×sUm×(r-s)], V=[Vn×sVn×(r-s)] are orthogonal matrices and
(37)σi(𝒜*y){=1,ifi∈J,∈[0,1],ifi∈J-,
where J:={i:σi(W)≠0} and J-:={1,2,…,r}∖J. Therefore, the optimal objective value of the optimization problem
(38)miny,γ{γ:𝒜*y∈∂∥W∥*,σi(𝒜*y){=1,ifi∈J,∈[0,γ],ifi∈J-,}
is at most one. For the given W with its SVD W=Um×sWsVn×sT, let(39)Π:={(0s00σ(M))conv{M∈ℝm×n:theSVDofMisM=[Um×sU-m×(r-s)](0s00σ(M))[Vn×sV-n×(r-s)]T}.It is easy to see that Π is a subspace and its normal cone (in the sense of variational analysis, see, e.g., [28] for details) is specified by Π⊥. Thus, the above problem (38) is equivalent to the following convex optimization problem with set constraint:
(40)miny,M{∥M∥:𝒜*y-Um×sVn×sT-M=0,M∈Π}.
We will show that the optimal value is less than 1. For a contradiction, suppose that the optimal value is one. Then, by [28, Theorem 10.1 and Exercise  10.52], there exists a Lagrange multiplier D∈ℝm×n such that the function
(41)L(y,M)=∥M∥+〈D,𝒜*y-Um×sVn×sT-M〉+δΠ(M)
has unconstrained minimum in (y,M) equal to 1, where δΠ(·) is the indicator function of Π. Let (y*,M*) be an optimal solution. Then, by the optimality condition 0∈∂L, we obtain that
(42)0∈∂yL(y*,M*),0∈∂ML(y*,M*).
Direct calculation yields that
(43)𝒜D=0,0∈-D+∂∥M*∥+Π⊥.
Then there exist DJ∈Π⊥ and DJ-∈∂∥M*∥ such that D=DJ+DJ-. Notice that [29, Corollary  6.4] implies that for DJ-∈∂∥M*∥, DJ-∈Π and ∥DJ-∥*≤1. Therefore, 〈D,Um×sVn×sT〉=〈DJ,Um×sVn×sT〉 and 〈D,M*〉=〈DJ-,M*〉. Moreover, 〈DJ-,M*〉≤∥M*∥ by the definition of the dual norm of ∥·∥. This together with the facts 𝒜D=0, DJ∈Π⊥ and DJ-∈∂∥M*∥⊆Π yields
(44)L(y*,M*)=∥M*∥-〈DJ-,M*〉+〈D,𝒜*y*〉-〈DJ,Um×sVn×sT〉+δΠ(M*)≥-〈DJ,Um×sVn×sT〉+δΠ(M*).
Thus, the minimum value of  L(y,M) is attained, L(y*,M*)=-〈DJ,Um×sVn×sT〉, when M*∈Π, 〈DJ-,M*〉=∥M*∥. We obtain that ∥DJ-∥*=1. By assumption, 1=L(y*,M*)=-〈DJ,Um×sVn×sT〉. That is, ∑i=1s‍(Um×sTDVn×s)ii=-1. Without loss of generality, let SVD of the optimal M* be M*=U~(0s00σ(M*))V~T, where U~:=[Um×sU~m×(r-s)] and V~:=[Vn×sV~n×(r-s)]. From the above arguments, we obtain that(i)
𝒜D=0,(ii)
∑i=1s‍(Um×sTDVn×s)ii=∑i∈J‍(U~TDV~)ii=-1,(iii)
∑i∈J-‍(U~TDV~)ii=1.
Clearly, for everyt∈ℝ, the matrices Xt:=W+tD are feasible in (6). Note that
(45)W=Um×sWsVn×sT=[Um×sU~m×(r-s)](Ws000)[Vn×sV~n×(r-s)]T.
Then, ∥W∥*=∥U~TWV~∥*=Tr(U~TWV~). From the above equations, we obtain that ∥Xt∥*=∥W∥* for all small enough t>0 (since σi(W)>0, i∈{1,2,…,s}). Noting that W is the unique optimal solution to (6), we have Xt=W, which means that (U~TDV~)ii=0 for i∈J. This is a contradiction, and hence the desired conclusion holds.
We next prove that𝒜 is s-good if γs(𝒜)<1. That is, we let W be an s-rank matrix and we show that W is the unique optimal solution to (6). Without loss of generality, let W be a matrix of rank s′≠0 and Um×s′Ws′Vn×s′T its SVD, where Um×s′∈ℝm×s′, Vn×s′∈ℝn×s′ are orthogonal matrices and Ws′=Diag((σ1(W),…,σs′(W))T). It follows from Proposition 4 that γs′(𝒜)≤γs(𝒜)<1. By the definition of γs(𝒜), there exists y∈ℝp such that 𝒜*y=UDiag(σ(𝒜*y))VT, where U=[Um×s′Um×(r-s′)], V=[Vn×s′Vn×(r-s′)], and(46)σi(𝒜*y){=1,ifσi(W)≠0,∈[0,1),ifσi(W)=0.
Now, we have the optimization problem of minimizing the function
(47)f(X)=∥X∥*-yT[𝒜X-𝒜W]=∥X∥*-〈𝒜*y,X〉+∥W∥*
over all X∈ℝm×n such that 𝒜X=𝒜W. Note that 〈𝒜*y,X〉≤∥X∥* by ∥𝒜*y∥≤1 and the definition of dual norm. So f(X)≥∥X∥*-∥X∥*+∥W∥*=∥W∥* and this function attains its unconstrained minimum in X at X=W. Hence X=W is an optimal solution to (6). It remains to show that this optimal solution is unique. Let Z be another optimal solution to the problem. Then f(Z)-f(W)=∥Z∥*-yT𝒜Z=∥Z∥*-〈𝒜*y,Z〉=0. This together with the fact ∥𝒜*y∥≤1 implies that there exist SVDs for 𝒜*y and Z such that
(48)𝒜*y=U~Diag(σ(𝒜*y))V~T,Z=U~Diag(σ(Z))V~T,
where U~∈ℝm×r and V~∈ℝn×r are orthogonal matrices, and σi(Z)=0 if σi(𝒜*y)≠1. Thus, for σi(𝒜*y)=0, for all i∈{s′+1,…,r}, we must have σi(Z)=σi(W)=0. By the two forms of SVDs of 𝒜*y as above, Um×s′Vn×s′T=U~m×s′V~n×s′T where U~m×s′, V~n×s′T are the corresponding submatrices of U~, V~, respectively. Without loss of generality, let
(49)U=[u1,u2,…,ur],V=[v1,v2,…,vr],U~=[u~1,u~2,…,u~r],V~=[v~1,v~2,…,v~r],
where uj=u~j and vj=v~j for the corresponding index j∈{i:σi(𝒜*y)=0,i∈{s′+1,…,r}}. Then we have
(50)Z=∑i=1s′‍σi(Z)u~iv~iT,W=∑i=1s′‍σi(W)uiviT.
From Um×s′Vn×s′T=U~m×s′V~n×s′T, we obtain that
(51)∑i=s′+1r‍σi(𝒜*y)u~iv~iT=∑i=s′+1r‍σi(𝒜*y)uiviT.
Therefore, we deduce
(52)∑i=s′+1,σi(𝒜*y)≠0r‍σi(𝒜*y)u~iv~iT+∑i=s′+1,σi(𝒜*y)=0r‍u~iv~iT=∑i=s′+1,σi(𝒜*y)≠0r‍σi(𝒜*y)uiviT+∑i=s′+1,σi(𝒜*y)=0r‍uiviT=:Ω.
Clearly, the rank of Ω is no less than r-s′≥r-s. From the orthogonality property of U,V and U~,V~, we easily derive that
(53)ΩTu~iv~iT=0,ΩTuiviT=0,∀i∈{1,2,…,s′}.
Thus, we obtain ΩT(Z-W)=0, which implies that the rank of the matrix Z-W is no more than s. Since γs(𝒜)<1, there exists y~ such that
(54)σi(𝒜*y~){=1,ifσi(Z-W)≠0,∈[0,1)ifσi(Z-W)=0.
Therefore, 0=y~T𝒜(Z-W)=〈𝒜*y~,Z-W〉=∥Z-W∥*. Then Z=W.For theG-number γ^s(𝒜), we directly obtain the following equivalent theorem of s-goodness from Proposition 5 and Theorem 7.Theorem 8.
Let𝒜:ℝm×n→ℝp be a linear transformation, and s∈{1,2,…,r}. Then 𝒜 is s-good if and only if γ^s(𝒜)<1/2.


## 4.s-Goodness, NSP, and RIP

This section deals with the connections betweens-goodness, the null space property (NSP), and the restricted isometry property (RIP). We start with establishing the equivalence of NSP and G-number γ^s(𝒜)<1/2. Here, we say 𝒜  satisfies NSP if for every nonzero matrix X∈Null(𝒜) with the SVD X=UDiag(σ(X))VT, then we have
(55)∑i=1s‍σi(X)<∑i=s+1r‍σi(X).
For further details, see, for example, [14, 19–21] and references therein.Proposition 9.
For the linear transformation𝒜, γ^s(𝒜)<1/2 if and only if 𝒜 satisfies NSP.Proof.
We first give an equivalent representation of theG-number γ^s(𝒜,β). We define a compact convex set first:
(56)Ps:={Z∈ℝm×n:∥Z∥*≤s,∥Z∥≤1}.
Let Bβ:={y∈ℝp:∥y∥d≤β} and B:={X∈ℝm×n:∥X∥≤1}. By definition, γ^s(𝒜,β) is the smallest γ such that the closed convex set Cγ,β:=𝒜*Bβ+γB contains all matrices with s nonzero singular values, all equal to 1. Equivalently, Cγ,β contains the convex hull of these matrices, namely, Ps. Note that γ satisfies the inclusion Ps⊆Cγ,β if and only if for every X∈ℝm×n(57)maxZ∈Ps〈Z,X〉≤maxY∈Cγ,β〈Y,X〉=maxy∈ℝp,W∈ℝm×n{〈X,𝒜*y〉+γ〈X,W〉:∥y∥d≤β,∥W∥≤1}=β∥𝒜X∥+γ∥X∥*.
For the above, we adopt the convention that whenever β=+∞, β∥𝒜X∥ is defined to be +∞ or 0 depending on whether ∥𝒜X∥>0 or ∥𝒜X∥=0. Thus, Ps⊆Cγ,β if and only if maxZ∈Ps{〈Z,X〉-β∥𝒜X∥}≤γ∥X∥*. Using the homogeneity of this last relation with respect to X, the above is equivalent to
(58)maxZ,X{〈Z,X〉-β∥𝒜X∥:Z∈Ps,∥X∥*≤1}≤γ.
Therefore, we obtain γ^s(𝒜,β)=maxZ,X{〈Z,X〉-β∥𝒜X∥:Z∈Ps,∥X∥*≤1}. Furthermore,
(59)γ^s(𝒜)=maxZ,X{〈Z,X〉:Z∈Ps,∥X∥*≤1,𝒜X=0}.
ForX∈ℝm×n with 𝒜X=0, let X=UDiag(σ(X))VT be its SVD. Then, we obtain the sum of the s largest singular values of X as
(60)∥X∥s,*=maxZ∈Ps〈Z,X〉.
From (59), we immediately obtain that γ^s(𝒜) is the best upper bound on ∥X∥s,* of matrices X∈Null(𝒜) such that ∥X∥*≤1. Therefore, γ^s(𝒜)<1/2 implies that the maximum value of ∥·∥s,*-norms of matrices X∈Null(𝒜) with ∥X∥*=1 is less than 1/2. That is, ∑i=1s‍σi(X)<1/2∑i=1r‍σi(X). Thus, ∑i=1s‍σi(X)<∑i=s+1r‍σi(X) and hence 𝒜 satisfies NSP. Now, it is easy to see that 𝒜 satisfies NSP if and only if γ^s(𝒜)<1/2.Next, we consider the connection between restricted isometry constants andG-number of the linear transformation in LMR. It is well known that, for a nonsingular matrix (transformation) T∈ℝp×p, the RIP constants of 𝒜 and T𝒜 can be very different, as shown by Zhang [30] for the vector case. However, the s-goodness properties of 𝒜 and T𝒜 are always the same for a nonsingular transformation T∈ℝp×p (i.e., s-goodness properties enjoy scale invariance in this sense). Recall that the s-restricted isometry constantδs of a linear transformation 𝒜 is defined as the smallest constant such that the following holds for all s-rank matrices X∈ℝm×n:
(61)(1-δs)∥X∥F2≤∥𝒜X∥22≤(1+δs)∥X∥F2.
In this case, we say 𝒜 possesses the RI(δs)-property (RIP) as in the CS context. For details, see [4, 31–34] and the references therein.Proposition 10.
Let𝒜:ℝm×n→ℝp be a linear transformation and s∈{0,1,2,…,r}. For any nonsingular transformation T∈ℝp×p, γ^s(𝒜)=γ^s(T𝒜).Proof.
It follows from the nonsingularity ofT that {X:𝒜X=0}={X:T𝒜X=0}. Then, by the equivalent representation of the G-number γ^s(𝒜,β) in (59),
(62)γ^s(𝒜)=maxZ,X{〈Z,X〉:Z∈Ps,∥X∥*≤1,𝒜X=0}=maxZ,X{〈Z,X〉:Z∈Ps,∥X∥*≤1,T𝒜X=0}=γ^s(T𝒜).For the RIP constantδ2s, Oymak et al. [21] gave the current best bound on the restricted isometry constant δ2s<0.472, where they proposed a general technique for translating results from SSR to LMR. Together with the above arguments, we immediately obtain the following theorem.Theorem 11.
δ
2
s
<
0.472
⇒
𝒜 satisfying NSP⇔γ^s(𝒜)<1/2⇔γs(𝒜)<1⇔𝒜 is s-good.Proof.
It follows from [21, Theorem  1], Proposition 9, and Theorems 7 and 8.The above theorem says thats-goodness is a necessary and sufficient condition for recovering the low-rank solution exactly via nuclear norm minimization.


## 5. Conclusion

In this paper, we have shown thats-goodness of the linear transformation in LMR is a necessary and sufficient conditions for exact s-rank matrix recovery via the nuclear norm minimization, which is equivalent to the null space property. Our analysis is based on the two characteristic s-goodness constants, γs and γ^s, and the variational property of matrix norm in convex optimization. This shows that s-goodness is an elegant concept for low-rank matrix recovery, although γs and γ^s may not be easy to compute. Development of efficiently computable bounds on these quantities is left to future work. Even though we develop and use techniques based on optimization, convex analysis, and geometry, we do not provide explicit analogues to the results of Donoho [35] where necessary and sufficient conditions for vector recovery special case were derived based on the geometric notions of face preservation and neighborliness. The corresponding generalization to low-rank recovery is not known, currently the closest one being [22]. Moreover, it is also important to consider the semidefinite relaxation (SDR) for the rank minimization with the positive semidefinite constraint since the SDR convexifies nonconvex or discrete optimization problems by removing the rank-one constraint. Another future research topic is to extend the main results and the techniques in this paper to the SDR.



---

*Source: 101974-2013-04-09.xml*