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 , 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.

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:

()

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):

()

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 ∈ ℝⁿ, is diagonal, the LMR (1) reduces to sparse signal recovery (SSR), which is the so-called cardinality minimization problem (CMP):

()

where ∥x∥₀ 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 ℓ₁-norm minimization relaxation (basis pursuit problem):

()

where ∥x∥₁ is the ℓ₁-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 X₀ can be recovered if and only if the null space of 𝒜 does not intersect the tangent cone of the nuclear norm ball at X₀.

In the setting of CS, there are other characterizations of the sensing matrix, under which ℓ₁-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 ℓ₁-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 , 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 is s-good.

Let W ∈ ℝ^m×n, r : = min {m, n}, and let W = U Diag(σ(W))V^T be an SVD of W, where U ∈ ℝ^m×r, V ∈ ℝ^n×r, and Diag(σ(W)) is the diagonal matrix of σ(W) = (σ₁(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,

()

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

as its SVD where U_m×s ∈ ℝ^m×s, V_n×s ∈ ℝ^n×s are orthogonal matrices and W_s = Diag((σ₁(W), …, σ_s(W)) ^T). For a vector y ∈ ℝ^p, let ∥·∥_d be the dual norm of ∥·∥ specified by ∥y∥_d : = max _v{〈v, y〉:∥v∥ ≤ 1}. In particular, ∥·∥_∞ is the dual norm of ∥·∥₁ 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

be the Frobenius norm of X, which is equal to the ℓ₂-norm of the vector of its singular values. We denote by X^T 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 to s-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

()

We denote by s_*(𝒜) 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 . We call γ_s and G-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 (i.e., s nonzero singular values, all equal to 1), there exists a vector y ∈ ℝ^p such that

()

where U = [U_m×s U_m×(r−s)], V = [V_n×s V_n×(r−s)] are orthogonal matrices, and

()

If there does not exist such y for some X as above, we set γ_s(𝒜, β) = +∞.

(ii) G-number 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:

()

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(𝒜),

instead of γ_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

()

Similarly, for every matrix X ∈ ℝ^m×n with s nonzero singular values, all equal to 1, there exists a vector

such that

and X share the same orthogonal row and column spaces:

()

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

satisfying (11).

2.2. Basic Properties of G-Numbers

In order to characterize the s-goodness of a linear transformation 𝒜, we study the basic properties of G-numbers. We begin with the result that G-numbers γ_s(𝒜, β) and are convex nonincreasing functions of β.

Proposition 3. For every linear transformation 𝒜 and every s ∈ {0,1, …, r}, G-numbers γ_s(𝒜, β) and 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 β₁, β₂ ∈ [0, +∞], we need to verify that

()

The above inequality follows immediately if one of β₁, β₂ is +∞. Thus, we may assume β₁, β₂ ∈ [0, +∞). In fact, from the argument around (10) and the definition of γ_s(𝒜, ·), we know that for every matrix X = U Diag(σ(X))V^T with s nonzero singular values, all equal to 1, there exist vectors y₁, y₂ ∈ ℝ^p such that for k ∈ {1,2}

()

It is immediate from (13) that

. Moreover, from the above information on the singular values of 𝒜^*y₁, 𝒜^*y₂, we may set 𝒜^*y_k = X + Y_k, k ∈ {1,2} such that

()

This implies that for every α ∈ [0,1]

()

and hence rank [αY₁ + (1 − α)Y₂] ≤ r − s, X, and [αY₁ + (1 − α)Y₂] have orthogonal row and column spaces. Thus, noting that 𝒜^*[αy₁ + (1 − α)y₂] = X + αY₁ + (1 − α)Y₂, we obtain that

and

()

for every α ∈ [0,1]. Combining this with the fact

()

we obtain the desired conclusion.

The following observation that G-numbers γ_s(𝒜, β), are nondecreasing in s is immediate.

Proposition 4. For every s^′ ≤ s, one has , .

We further investigate the relationship between the G-numbers γ_s(𝒜, β) and .

Proposition 5. Let 𝒜 : ℝ^m×n → ℝ^p be a linear transformation, β ∈ [0, +∞], and s ∈ {0,1, 2, …, r}. Then one has

()

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 . Then we have and

()

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

()

Now, we assume that

. 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 S_J with respect to orthogonal matrices U, V as

()

In the above,

denotes the complement of J. It is immediately seen that S_J is a closed convex set in ℝ^r. Moreover, we have the following

Claim 1. S_J contains the ∥·∥_∞-ball of radius centered at the origin in ℝ^r.

Proof. Note that S_J is closed and convex. Moreover, S_J is the direct sum of its projections onto the pair of subspaces

()

Let Q denote the projection of S_J onto L_J. Then, Q is closed and convex (because of the direct sum property above and the fact that S_J is closed and convex). Note that L_J can be naturally identified with ℝ^s, and our claim is the image

of Q under this identification that contains the ∥·∥_∞-ball B_s of radius

centered at the origin in ℝ^s. For a contradiction, suppose B_s is not contained in

. Then there exists

. Since

is closed and convex, by a separating hyperplane theorem, there exists a vector u ∈ ℝ^s, ∥u∥₁ = 1 such that

()

Let z ∈ ℝ^r be defined by

()

By definition of

, for s-rank matrix U Diag(z)V^T, there exists y ∈ ℝ^p such that ∥y∥_d ≤ β and

()

where W and U Diag(z)V^T have the same orthogonal row and column spaces,

and

. Together with the definitions of S_J and

, this means that

contains a vector

with

, ∀i ∈ {1,2, …, s}. Therefore,

()

By v ∈ B_s and the definition of u, we obtain

()

where the strict inequality follows from the facts that

and u separates v from

. The above string of inequalities is a contradiction, and hence the desired claim holds.

Using the above claim, we conclude that for every J⊆{1,2, …, r} with cardinality s, there exists an x ∈ S_J such that , for all i ∈ J. From the definition of S_J, we obtain that there exists y ∈ ℝ^p with such that

()

where

if i ∈ J, and

. Thus, we obtain that

()

To conclude the proof, we need to prove that the inequalities we established

()

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 , 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∥₁ ≤ ρ}. Then for every s ∈ {1,2, …, r}

()

Proof. Fix s ∈ {1,2, …, r}. We only need to show the first implication. Let γ : = γ_s(𝒜) < 1. Then for every matrix W ∈ ℝ^m×n with its SVD , there exists a vector y ∈ ℝ^p such that

()

where U = [U_m×s U_m×(r−s)], V = [V_n×s V_n×(r−s)] are orthogonal matrices, and

()

Clearly, ∥𝒜^*y∥ ≤ 1. That is,

()

From the inclusion assumption, we obtain that

()

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 of s-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 be its SVD where U_m×s ∈ ℝ^m×s, V_n×s ∈ ℝ^n×s are orthogonal matrices and W_s = Diag((σ₁(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 f_y(x) = ∥X∥_* − y^T[𝒜X − 𝒜W] attains its minimum value over X ∈ ℝ^m×n at X = W. So 0 ∈ ∂f_y(W) or 𝒜^*y ∈ ∂∥W∥_*. Using the fact (see, e.g., [27])

()

it follows that there exist matrices U_m×(r−s), V_n×(r−s) such that 𝒜^*y = U Diag(σ_i(𝒜^*y))V^T where U = [U_m×s U_m×(r−s)], V = [V_n×s V_n×(r−s)] are orthogonal matrices and

()

where J : = {i : σ_i(W) ≠ 0} and

. Therefore, the optimal objective value of the optimization problem

()

is at most one. For the given W with its SVD

, let

()

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:

()

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

()

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

()

Direct calculation yields that

()

Then there exist D_J ∈ Π^⊥ and

such that

. Notice that [29, Corollary 6.4] implies that for

and

. Therefore,

and

. Moreover,

by the definition of the dual norm of ∥·∥. This together with the facts 𝒜D = 0, D_J ∈ Π^⊥ and

yields

()

Thus, the minimum value of L(y, M) is attained,

, when M^* ∈ Π,

. We obtain that

. By assumption,

. That is,

. Without loss of generality, let SVD of the optimal M^* be

, where

and

. From the above arguments, we obtain that

(i)
𝒜D = 0,
(ii)
,
(iii)
.

Clearly, for every t ∈ ℝ, the matrices X_t : = W + tD are feasible in (6). Note that

()

Then,

. From the above equations, we obtain that

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 X_t = W, which means that

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 its SVD, where , are orthogonal matrices and . It follows from Proposition 4 that . By the definition of γ_s(𝒜), there exists y ∈ ℝ^p such that 𝒜^*y = U Diag(σ(𝒜^*y))V^T, where , , and

()

Now, we have the optimization problem of minimizing the function

()

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∥_* − y^T𝒜Z = ∥Z∥_* − 〈𝒜^*y, Z〉 = 0. This together with the fact ∥𝒜^*y∥ ≤ 1 implies that there exist SVDs for 𝒜^*y and Z such that

()

where

and

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,

where

are the corresponding submatrices of

, respectively. Without loss of generality, let

()

where

and

for the corresponding index j ∈ {i : σ_i(𝒜^*y) = 0, i ∈ {s^′ + 1, …, r}}. Then we have

()

From

, we obtain that

()

Therefore, we deduce

()

Clearly, the rank of Ω is no less than r − s^′ ≥ r − s. From the orthogonality property of U, V and

, we easily derive that

()

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

such that

()

Therefore,

. Then Z = W.

For the G-number , 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 .

4. s-Goodness, NSP, and RIP

This section deals with the connections between s-goodness, the null space property (NSP), and the restricted isometry property (RIP). We start with establishing the equivalence of NSP and G-number

. Here, we say 𝒜 satisfies NSP if for every nonzero matrix X ∈ Null(𝒜) with the SVD X = U Diag(σ(X))V^T, then we have

()

For further details, see, for example, [14, 19–21] and references therein.

Proposition 9. For the linear transformation 𝒜, if and only if 𝒜 satisfies NSP.

Proof. We first give an equivalent representation of the G-number . We define a compact convex set first:

()

Let B_β : = {y ∈ ℝ^p : ∥y∥_d ≤ β} and B : = {X ∈ ℝ^m×n : ∥X∥ ≤ 1}. By definition,

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, P_s. Note that γ satisfies the inclusion P_s⊆C_γ,β if and only if for every X ∈ ℝ^m×n

()

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, P_s⊆C_γ,β if and only if

. Using the homogeneity of this last relation with respect to X, the above is equivalent to

()

Therefore, we obtain

. Furthermore,

()

For X ∈ ℝ^m×n with 𝒜X = 0, let X = U Diag(σ(X))V^T be its SVD. Then, we obtain the sum of the s largest singular values of X as

()

From (59), we immediately obtain that

is the best upper bound on ∥X∥_s,* of matrices X ∈ Null(𝒜) such that ∥X∥_* ≤ 1. Therefore,

implies that the maximum value of ∥·∥_s,*-norms of matrices X ∈ Null(𝒜) with ∥X∥_* = 1 is less than 1/2. That is,

. Thus,

and hence 𝒜 satisfies NSP. Now, it is easy to see that 𝒜 satisfies NSP if and only if

Next, we consider the connection between restricted isometry constants and G-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:

()

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, .

Proof. It follows from the nonsingularity of T that {X : 𝒜X = 0} = {X : T𝒜X = 0}. Then, by the equivalent representation of the G-number in (59),

()

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. δ_2s < 0.472⇒𝒜 satisfying is s-good.

Proof. It follows from [21, Theorem 1], Proposition 9, and Theorems 7 and 8.

The above theorem says that s-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 that s-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 , 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 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.

Acknowledgments

The authors thank two anonymous referees for their very useful comments. The work was supported in part by the National Basic Research Program of China (2010CB732501), the National Natural Science Foundation of China (11171018), a Discovery Grant from NSERC, a research grant from the University of Waterloo, ONR research Grant N00014-12-10049, and the Fundamental Research Funds for the Central Universities (2011JBM306, 2013JBM095).

References

1 Beck C. and D’Andrea R., Computational study and comparisons of LFT reducibility methods, Proceedings of the American Control Conference, June 1998, Philadelphia, Pa, USA.
Google Scholar
2 Mesbahi M. and Papavassilopoulos G. P., On the rank minimization problem over a positive semidefinite linear matrix inequality, IEEE Transactions on Automatic Control. (1997) 42, no. 2, 239–243, https://doi.org/10.1109/9.554402, MR1438452, ZBL0872.93029.
10.1109/9.554402
Web of Science® Google Scholar
3 Fazel M., Hindi H., and Boyd S. P., A rank minimization heuristic with application to minimum order system approximation, Proceedings of American Control Conference, June 2001, 4734–4739, 2-s2.0-0034853839.
Google Scholar
4 Recht B., Fazel M., and Parrilo P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review. (2010) 52, no. 3, 471–501, https://doi.org/10.1137/070697835, MR2680543, ZBL1198.90321.
10.1137/070697835
Web of Science® Google Scholar
5 Ames B. P. W. and Vavasis S. A., Nuclear norm minimization for the planted clique and biclique problems, Mathematical Programming. (2011) 129, no. 1, 69–89, https://doi.org/10.1007/s10107-011-0459-x, MR2831403.
10.1007/s10107-011-0459-x
Web of Science® Google Scholar
6 Cai J.-F., Candès E. J., and Shen Z., A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization. (2010) 20, no. 4, 1956–1982, https://doi.org/10.1137/080738970, MR2600248, ZBL1201.90155.
10.1137/080738970
Web of Science® Google Scholar
7 Candès E. J. and Recht B., Exact matrix completion via convex optimization, Foundations of Computational Mathematics. (2009) 9, no. 6, 717–772, https://doi.org/10.1007/s10208-009-9045-5, MR2565240, ZBL1219.90124.
10.1007/s10208-009-9045-5
Web of Science® Google Scholar
8 Ding C., Sun D., and Toh K. C., An introduction to a class of matrix cone programming, 2010.
Google Scholar
9 Lin Z., Chen M., Wu L., and Ma Y., The augmented Lagrange multiplier method for exact recovery of a corrupted low-rank matrices, http://arxiv.org/abs/1009.5055.
Google Scholar
10 Liu Y., Sun D., and Toh K. C., An implementable proximal point algorithmic framework for nuclear norm minimization, Mathematical Programming. (2012) 133, no. 1-2, 399–436, https://doi.org/10.1007/s10107-010-0437-8.
10.1007/s10107-010-0437-8
Web of Science® Google Scholar
11 Liu Z. and Vandenberghe L., Interior-point method for nuclear norm approximation with application to system identification, SIAM Journal on Matrix Analysis and Applications. (2009) 31, no. 3, 1235–1256, https://doi.org/10.1137/090755436, MR2558821.
10.1137/090755436
Web of Science® Google Scholar
12 Ma S., Goldfarb D., and Chen L., Fixed point and Bregman iterative methods for matrix rank minimization, Mathematical Programming. (2011) 128, no. 1-2, 321–353, https://doi.org/10.1007/s10107-009-0306-5, MR2810961, ZBL1221.65146.
10.1007/s10107-009-0306-5
Web of Science® Google Scholar
13 Peng Y., Ganesh A., Wright J., Xu W., and Ma Y., RASL: robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE Transactions on Pattern Analysis and Machine Intelligence. (2010) 34, no. 1, 2233–2246, https://doi.org/10.1109/TPAMI.2011.282.
10.1109/TPAMI.2011.282
Web of Science® Google Scholar
14 Recht B., Xu W., and Hassibi B., Necessary and sufficient conditions for success of the nuclear norm heuristic for rank minimization, Proceedings of the 47th IEEE Conference on Decision and Control (CDC ′08), December 2008, Cancun, Mexico, 3065–3070, 2-s2.0-62949189702, https://doi.org/10.1109/CDC.2008.4739332.
10.1109/CDC.2008.4739332
Google Scholar
15 Tao M. and Yuan X., Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM Journal on Optimization. (2011) 21, no. 1, 57–81, https://doi.org/10.1137/100781894, MR2765489, ZBL1218.90115.
10.1137/100781894
Web of Science® Google Scholar
16 Candès E. J., Romberg J., and Tao T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory. (2006) 52, no. 2, 489–509, https://doi.org/10.1109/TIT.2005.862083, MR2236170, ZBL1231.94017.
10.1109/TIT.2005.862083
Web of Science® Google Scholar
17 Candes E. J. and Tao T., Decoding by linear programming, IEEE Transactions on Information Theory. (2005) 51, no. 12, 4203–4215, https://doi.org/10.1109/TIT.2005.858979, MR2243152.
10.1109/TIT.2005.858979
Web of Science® Google Scholar
18 Donoho D. L., Compressed sensing, IEEE Transactions on Information Theory. (2006) 52, no. 4, 1289–1306, https://doi.org/10.1109/TIT.2006.871582, MR2241189, ZBL1163.94399.
10.1109/TIT.2006.871582
Web of Science® Google Scholar
19 Recht B., Xu W., and Hassibi B., Null space conditions and thresholds for rank minimization, Mathematical Programming. (2011) 127, no. 1, 175–202, https://doi.org/10.1007/s10107-010-0422-2, MR2776714, ZBL1211.90172.
10.1007/s10107-010-0422-2
Web of Science® Google Scholar
20 Oymak S. and Hassibi B., New null space results and recovery thresholds for matrix rank minimization, http://arxiv.org/abs/1011.6326.
Google Scholar
21 Oymak S., Mohan K., Fazel M., and Hassibi B., A simplified approach to recovery conditions for low-rank matrices, Proceedings of International Symposium on Information Theory (ISIT ′11), August 2011, 2318–2322.
Google Scholar
22 Chandrasekaran V., Recht B., Parrilo P. A., and Willsky A. S., The convex geometry of linear inverse problems, Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing, 2011.
Google Scholar
23 d′Aspremont A. and El Ghaoui L., Testing the nullspace property using semidefinite programming, Mathematical Programming. (2011) 127, no. 1, 123–144, https://doi.org/10.1007/s10107-010-0416-0, MR2776712, ZBL1211.90167.
10.1007/s10107-010-0416-0
Web of Science® Google Scholar
24 Juditsky A. and Nemirovski A., On verifiable sufficient conditions for sparse signal recovery via ℓ₁ minimization, Mathematical Programming. (2011) 127, no. 1, 57–88, https://doi.org/10.1007/s10107-010-0417-z, MR2776710, ZBL1211.90333.
10.1007/s10107-010-0417-z
Web of Science® Google Scholar
25 Juditsky A., Karzan F., and Nemirovski A., Verifiable conditions of ℓ₁-recovery for sparse signals with sign restrictions, Mathematical Programming. (2011) 127, no. 1, 89–122, https://doi.org/10.1007/s10107-010-0418-y, MR2776711.
10.1007/s10107-010-0418-y
Web of Science® Google Scholar
26 Juditsky A., Karzan F., and Nemirovski A. S., Accuracy guarantees for ℓ₁-recovery, IEEE Transactions on Information Theory. (2011) 57, no. 12, 7818–7839.
10.1109/TIT.2011.2162569
Web of Science® Google Scholar
27 Watson G. A., Characterization of the subdifferential of some matrix norms, Linear Algebra and Its Applications. (1992) 170, 33–45, https://doi.org/10.1016/0024-3795(92)90407-2, MR1160950, ZBL0751.15011.
10.1016/0024-3795(92)90407-2
Web of Science® Google Scholar
28 Rockafellar R. T. and Wets R. J.-B., Variational Analysis, 2004, 2nd edition, Springer, New York, NY, USA.
Google Scholar
29 Lewis A. S. and Sendov H. S., Nonsmooth analysis of singular values. II. Applications, Set-Valued Analysis. (2005) 13, no. 3, 243–264, https://doi.org/10.1007/s11228-004-7198-6, MR2162513, ZBL1129.49026.
10.1007/s11228-004-7198-6
Google Scholar
30 Zhang Y., Theory of Compressive Sensing via L₁-Minimization: A Non-RIP Analysis and Extensions, 2008.
Google Scholar
31 Candès E. J. and Plan Y., Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements, IEEE Transactions on Information Theory. (2011) 57, no. 4, 2342–2359, https://doi.org/10.1109/TIT.2011.2111771, MR2809094.
10.1109/TIT.2011.2111771
Web of Science® Google Scholar
32 Lee K. and Bresler Y., Guaranteed minimum rank approximation from linear observations by nuclear norm minimization with an ellipsoidal constraint, http://arxiv.org/abs/0903.4742.
Google Scholar
33 Meka R., Jain P., and Dhillon I. S., Guaranteed rank minimization via singular value projection, http://arxiv.org/abs/0909.5457.
Google Scholar
34 Mohan K. and Fazel M., New restricted isometry results for noisy low-rank matrix recovery, Proceedings of IEEE International Symposium on Information Theory (ISIT ′10), June 2010, Austin, Tex, USA.
Google Scholar
35 Donoho D. L., Neighborly polytopes and sparse solution of underdetermined linear equations, 2004.
Google Scholar

All articles

s-Goodness for Low-Rank Matrix Recovery

Abstract

1. Introduction

2. Definitions and Basic Properties

2.1. Definitions

2.2. Basic Properties of G-Numbers

3. s-Goodness and G-Numbers

4. s-Goodness, NSP, and RIP

5. Conclusion

Acknowledgments

References

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

s-Goodness for Low-Rank Matrix Recovery

Abstract

1. Introduction

2. Definitions and Basic Properties

2.1. Definitions

2.2. Basic Properties of G-Numbers

3. s-Goodness and G-Numbers

4. s-Goodness, NSP, and RIP

5. Conclusion

Acknowledgments

References

References

Related

Information