Guarantees of Augmented Trace Norm Models in Tensor Recovery

1 Introduction

Low-rank tensor recovering problem is the generalization of sparse vector recovery and low-rank matrix recover to tensor data [Gandy et al., 2011; Tomioka et al., 2010; Liu et al., 2009]. It has drawn lots of attention from researchers in different fields in the past several years. It is not only a simple mathematical generalization of sparse vector recovery and low-rank matrix recover. They have wide applications in science and engineering, e.g. multimedia signal processing (compression, image in-painting, BRDF data estimation), machine learning (collaborative filtering), and bioinformatics (EEG signal analysis). The fundamental problem of low-rank tensor recovery is to find a tensor of (nearly) lowest rank from an underdetermined F(X) = b, where F is a linear operator and X ∈ RI1×I2×···×IN is a N-way tensor. Although researchers have proposed several algorithms to solve the problem, there're only a few results about the theory part, that is under what conditions the underline tensor data will be recovered exactly.

To recover a low-rank tensor X 0 ∈ RI1×I2×···×IN from linear measurements b = F(X 0 ), a powerful approach is the convex model [Gandy et al., 2011; Liu et al., 2009]

∗Ziqiang Shi is, now, with the Fujitsu Research & Development Center, Beijing, China.

where

and X(i) is the mode-i unfolding of X, ‖X(i)‖∗ is the trace norm of the matrix X(i), i.e. the sum of the singular values of X(i). For vector b with noise or generated by an approximately low-rank tensor, a variant of (1) is [Liu et al., 2009]

Despite empirical success, the recovery guarantees of tensor recovery algorithms has not been fully elucidated. Recently, several authors [Lai and Yin, 2012; Recht et al., 2007; Mo and Li, 2011] have got excellent results in the guarantees of sparse vector and low-rank matrix recovery . In this paper, we try to generalize these results to low-rank tensor recovery.

This paper mainly studies the guarantees of minimization of the augmented objective ‖X‖∗+ 1 2α ‖X‖2F . The augmented model for (1) and (3) are

and

respectively. These are natural generalizations of the augmented model for vector and matrix data [Lai and Yin, 2012] to tensor case.

Tomioka et. al. [Tomioka et al., 2010] analyzed the statistical performance of a tensor decomposition algorithm in the setting of random Gaussian design. But they didn't give results about general linear operator F. Our work gives results about that the general linear operator F, that is under what kind of the null-space property, the restricted isometry property (RIP), and the spherical section property, the tensor can be exactly recovered. And furthermore we give results both for the original and augmented model. To our best knowledge, this is the first work to extend the RIP, the nullspace property, and the spherical section property based results from the sparse vector recovery to tensor case. At last we should say this is not a trivial extension, because of the dependency among multiple constraints in different dimensions of tensor data, and we only obtain sufficient conditions for the exact tensor recovery, while for the matrix case, the conditions are also necessary. The sufficient and necessary condition is a challenge.

2 Notations

We adopt the nomenclature mainly used by Kolda and Bader on tensor decompositions and applications [Kolda and Bader, 2009], and also a few symbols of [De Lathauwer et al., 2000; Tomioka et al., 2011].

The order N of a tensor is the number of dimensions, also known as ways or modes. Matrices (tensor of order two) are denoted by upper case letters, e.g. X, and lower case letters for the elements, e.g. xij. Higher-order tensors (order three or higher) are denoted by Euler script letters, e.g. X, and element (i1, i2, · · · , iN) of a N-order tensor X is denoted by xi1i2···iN . Fibers are the higher-order analogue of matrix rows and columns. A fiber is defined by fixing every index but one. The mode-n fibers are all vectors xi1···in-1:in+1···iN that obtained by fixing the values of {i1, i2, · · · , iN} \ in. The mode-n unfolding, also knows as matricization, of a tensor X ∈ RI1×I2×···×IN is denoted by X(n) and arranges the model-n fibers to be the columns of the resulting matrix. The unfolding operator is denoted as unfold(·). The opposite operation is refold(·), denotes the refolding of the matrix into a tensor. The tensor element (i1, i2, · · · , iN) is mapped to the matrix element (in, j), where

Therefore, X(n) ∈ RIn×I1···In-1In+1···IN . The n-rank of a N-dimensional tensor X, denoted as rankn(X) is the column rank of X(n), i.e. the dimension of the vector space spanned by the mode-n fibers. We say a tensor X is rank (r1, ..., rN) when rk = rankk(X) for k = 1, ...,N, and denoted as rank(X). We introduce an ordering among tensors by the rank:rank(X) ≤ rank(Y) ⇔ (rank1(X), ..., rankN(X)) ⪯ (rank1(Y), ..., rankN(Y)) ⇔ ranki(X) ≤ ranki(Y), i = 1, ...,N. The inner product of two same-size tensors X, Y ∈ RI1×I2×···×IN is defined as vec(X)⊤ · vec(Y), where vec is a vectorization. The corresponding norm is ‖X‖F = √< X , X >, which is often called the Frobenius norm.

The n-th mode product of a tensor X ∈ RI1×I2×···×IN with a matrix U ∈ RJ×In is denoted by X ×n U and is of size I1 × ... × In-1 × J × In+1 × · · · × IN . Elementwise, we have

Every tensor can be written as the product [De Lathauwer et al., 2000]

in which:

• U (n) is a unitary In × In matrix,
• S is a I1 ×I2 × · · · ×IN-tensor of which the subtensors Sin=α, obtained by fixing the n-th index to α, have the properties of:

1) all-orthogonality: two subtensors Sin=α and Sin=β are orthogonal for all possible values of n, α and β subject to α ̸= β: < Sin=α, Sin=β >= 0,

The Frobenius norms ‖Sin=i‖F , symbolized by σ(n) i , are mode-n singular values of A, that means the singular values of A(n).

This is called the higher-order singular value decomposition (HOSVD) of a tensor A in [De Lathauwer et al., 2000]. Some properties of this HOSVD which will be used in this paper are listed below as lemmas:

Lemma 1. ([De Lathauwer et al., 2000] Property 6). Let the HOSVD of A be given as in (7), and let rn be equal to the highest index for which ‖Sin=rn ‖F > 0; then one has rank(A(n)) = rn.

Lemma 2. ( [De Lathauwer et al., 2000] Property 8). Let the HOSVD of A be given as in (7); due to the unitarily invariant

of the Frobenius norm, one has ‖A‖2F = I1∑ i=1 (σ(1) i )2 = ... = = ‖S‖2F .

3 Motivations and contributions

To explain why model (4) is interesting, we conducted following tensor completion simulations

to compare it with model (1) based tensor completion

The facade image data of [Liu et al., 2009] was used here to be an example. For color image has RGB values in each pixel, so it is indeed a 3-way tensor. Models (8) and (9) were solved to high accuracy by the solver LRTC [Liu et al., 2009]. For each model, we measured and recorded

The relative errors are depicted as functions of the number of iterations in Figure 1(a).

Motivated by the above example, we show in this paper that any α ≥ 10max i ‖X0 (i) ‖2 guarantees that problem (4) either recovers X 0 exactly or returns an approximate of it nearly as good as the solution of problem (1). Specifically, we show that several properties of F, such as the null-space property (a simple condition used in, e.g., [Liu et al., 2009; Donoho and Huo, 2001; Gribonval and Nielsen, 2003; Zhang, 2005; Oymak et al., 2011]), the restricted isometry principle [Candes and Tao, 2005], and the spherical section property [Zhang, 2008], which have been used in the recovery guarantees for vectors and matrices, can also guarantee the tensor recovery by model (1) and (4).

Figure 1: Facade in-painting.

Even though X 0 not known when α is set, max i ‖X0 (i) ‖2 is often easy to estimate. When max i ‖X0 (i) ‖2 is not available, using inequalities ‖X 0 ‖F ≥ max i ‖X0 (i) ‖2, one gets the more conservative formulae α ≥ 10‖X 0 ‖F . Furthermore, when F satisfies the RIP, one has ‖X 0 ‖F ≤ β‖b‖2 for some β > 0; hence, one has the option to use the even more conservative formula α ≥ 10β‖b‖2.

4 Tensor recovery guarantees

This section establishes recovery guarantees for the original and augmented trace norm models (1) and (4). The results are given based on the properties of F including the null-space property (NSP) in Theorem 5 and 6, the restricted isometry principle (RIP) [Candes and Tao, 2005] in Theorem 8 and 9, the spherical section property (SSP) [Zhang, 2008] in Theorem 10. These results adapt and generalize of the work in [Lai and Yin, 2012].

4.1 Null space property

The wide use of NSP for recovering sparse vector and lowrank matrices can be found in e.g. [Donoho and Huo, 2001; Gribonval and Nielsen, 2003; Zhang, 2005; Oymak et al., 2011]. In this subsection, we extend the NSP conditions on F for tensor recovery. Throughout this subsection, we let σi(X), i = 1, ...,m denote the i-th largest singular value of matrix X of rank m or less, and Σ(X) = diag(σ1(X), ..., σm(X)) denote the diagonal matrix of singular values and s(X) = (σ1(X), ..., σm(X)). ‖X‖2 = σ1(X) denotes the spectral norms of X.

We will need the following two technical lemmas for the introduction of the tensor NSP conditions.

Lemma 3. ([Horn and Johnson, 1990] Theorem 7.4.51). Let X and Y be two matrices of the same size. Then we have

and

Lemma 4. ([Lai and Yin, 2012] Equation (19)). Let x and h be two vectors of the same size, S := supp(x) and Z = S c . Here S is the index set of the nonzero support of x, and S c is the complement of S. Then we have

and

Now we give an NSP type sufficient condition for problem (1).

Theorem 5. (Tensor NSP condition for (1)). Assume X 0 is fixed, problem (1) uniquely recovers all tensors X 0 of rank (r1, ..., rN) or less from the measurements F(X 0 ) = b, if all H ∈ Null(F)\{0} satisfy

We can extend this result to problem (4) as follows.

Theorem 6. (Tensor NSP condition for (4)). Assume X 0 is fixed, problem (4) uniquely recovers all tensors X 0 of rank (r1, ..., rN) or less from the measurements F(X 0 ) = b, if all H ∈ Null(F)\{0} satisfy

Remark 1. For any finite α > 0, (16) is stronger than (15) due to the extra term ‖X0 (i) ‖2 α . Since various uniform recovery results establish conditions that guarantee (15), one can tighten these conditions so that they guarantee (16) and thus the uniform recovery by problem (4). How much tighter these conditions have to be depends on the value ‖X0 (i) ‖2 α .

4.2 Tensor restricted isometry principle

In this subsection, we generalize the RIP-based guarantees to tensor case and show that any α ≥ 10max i ‖X0 (i) ‖2 guarantees exact recovery by (4).

Definition 1. (Tensor RIP). Let M(r1,r2,...,rN) := {X ∈ RI1×I2×···×IN : rank(X(n)) ≤ rn, n = 1, ...,N}. The RIP constant δ(r1,r2,...,rN) of linear operator F is the smallest value such that

holds for all X ∈M(r1,r2,...,rN).

The following recovery theorems will characterize the power of the tensor restricted isometry constants. The first theorem generalizes Lemma 1.3 in [Candes and Tao, 2005] and Theorem 3.2 in[Recht et al., 2007] to low-rank tensor recovery.

Theorem 7. Suppose δ(2r1,2r2,...,2rN) < 1 for some (r1, r2, ..., rN) ⪰ (1, 1, ..., 1). Then X 0 is the only tensor of rank at most (r1, r2, ..., rN) satisfying F(X) = b.

The proof of the preceding theorem is identical to the argument given by Candes and Tao and is an immediate consequence of our definition of the constant δ(r1,r2,...,rN). No adjustment is necessary in the transition from sparse vectors and low-rank matrices to low-rank tensors. The key property used is the sub-additivity of the rank. Adapting results in [Lai and Yin, 2012; Mo and Li, 2011], we give the uniform recovery conditions for (1) below.

Theorem 8. (RIP condition for exact recovery by (1)). Let X 0 be a tensor with rank (r1, r2, ..., rN) or less. Problem (1) exactly recovers X 0 from measurements b = F(X 0 ) if F satisfies the RIP with δ(I1,...,2rn,...,IN) < 0.4931, for n = 1, ...N.

Next we carry out a similar study for the augmented model (4).

Theorem 9. (RIP condition for exact recovery by (4)). Let X 0 be a tensor with rank (r1, r2, ..., rN) or less. The augmented model (3) exactly recovers X 0 from measurements b = F(X 0 ) if F satisfies the RIP with δ(I1,...,2rn,...,IN) < 0.4404, n = 1, ...N and α ≥ 10 max i ‖X0 (i) ‖2.

Remark 2. Different values of δ(I1,...,2rn,...,IN), n = 1, ...N are associated with different conditions on α. Following (34), if δ(I1,...,2rn,...,IN) < 0.4715, n = 1, ...N, α ≥ 10max i ‖X0 (i) ‖2 guarantees exact recovery. If δ(I1,...,2rn,...,IN) < 0.1273, n = 1, ...N, α ≥ 10 max i ‖X0 (i) ‖2 guarantees exact recovery. In general, smaller δ(I1,...,2rn,...,IN), n = 1, ...N allows a smaller α.

4.3 Spherical section property

Next, we derive exact conditions based on the spherical section property (SSP) [Lai and Yin, 2012; Zhang, 2008]. There is not much discussion on spherical section property (SSP) for low-rank tensor recovery in the literature, here we present an SSP-based result.

Theorem 10. (SSP condition for exact recovery by (4)). Let F : RI1×I2×···×IN → Rm be a linear operator. Suppose there exists △ > 0 such that all nonzero nonzero H ∈ Null(F) satisfy

Assume that ‖X0 (i) ‖2, (i = 1, ..., N) and α > 0 are fixed. If

then the null-space condition holds for all nonzero H ∈ Null(F). Hence is sufficient for problem to recover any X 0 with rank (r1, r2, ..., rN) or less from measurements b = F(X 0 ).

5 Conclusion

In this work we focussed on the recovery guarantees of tensor recovery via convex optimization. We presented general results stating that the extension of some sufficient conditions for the recovery of low-rank matrices using nuclear norm minimization is also sufficient for the recovery of lowrank tensors using tensor nuclear norm minimization. We extended the null-space property, the restricted isometry principle, and the spherical section property conditions to the augmented tensor recovery problems, and find that any α ≥ 10 max i ‖X0 (i) ‖2 guarantees that problem (4) either recovers X 0 exactly or returns an approximate of it nearly as good as the solution of problem (1).

There are some directions that the current study can be extended. In this paper, we have focused on the recovery guarantees of the exact case; it would be meaningful to also analyze the guarantees for the stable recovery. Second, generalize the linearized Bregman algorithm [Yin et al., 2008] for augmented sparse vector and low-rank matrix recovery [Lai and Yin, 2012] to low-rank tensor case. Moreover, from our results, there is a big "gap" between the recovery conditions for matrices and tensors, and we need to fill this "gap" in future work. In a broader context, we believe that the current paper could serve as a basis for examining the augmented trace normmodels in tensor recovery.

Appendix

Proof of Theorem 5.

Proof. Pick any tensor X 0 of rank (r1, ..., rN) or less and let b = F(X 0 ). For any H ∈ Null(F)\{0}, we have F(X 0 +

H) = F(X 0 ) = b. By using (11), we have

where the first inequality follows from (11). For any nonzero H ∈ Null(F), ‖H‖2F > 0. Hence from (15) and (20), it follows that X 0 is a unique minimizer of (1).

Proof of Theorem 6.

Proof. Pick any tensor X 0 of rank (r1, ..., rN) or less and let b = F(X 0 ). For any nonzero H ∈ Null(F), we have F(X 0 +H) = F(X 0 ) = b. Thus

where the first inequality follows from (11) and (12), and the second inequality follows from (13) and (14). For any nonzero H ∈ Null(F), ‖H‖2F > 0. Hence, from (21) and (16), it follows that X 0 + H leads to a strictly worse objective than X 0 . That is, X 0 is the unique solution to problem (4).

Proof of Theorem 7.

Proof. Assume, on the contrary, that there exists a tensor with rank (r1, r2, ..., rN) or less satisfying F(X) = b and X ̸= X0. Then Z := X -X0 is a nonzero tensor of rank at most

(2r1, 2r2, ..., 2rN), and F(Z) = 0. But then we would have 0 = ‖F(Z)‖22 ≥ (1 - δ(2r1,2r2,...,2rN))‖Z‖2F > 0 which is a contradiction.

Proof of Theorem 8.

Proof. For any nonzero H ∈ Null(F), ‖H‖F > 0, let H = S ×1 U (1) ×2 U (2) ... ×N U (N) be the HOSVD of H. From Proposition 3.7 of [Kolda, 2006] we have rank(H(n)) ≤ rank(S(n)), (n = 1, .., N), thus we have rank(H) ⪯ rank(S). We decompose H = H0 + H1 + ..., where

and S{in:α} is the tensor obtained by fixing the n-th index to the index set α, others to zero. Similarly we have rank(H)i ⪯ rank(S{in:irn+1,...,(i+1)rn}) ⪯ (I1, ..., rn, ..., In), (i = 0, 1, ...). Due to the unitarily invariant of the Frobenius norm, we have ‖H0‖F = ‖S{in:1,...,rn}‖F , ‖H1‖F = ‖S{in:rn+1,...,2rn}‖F , .... Let h = (σ(n) 1 , σ(n) 2 , ..., σ(n) In ) and h0 = (σ(n) 1 , ..., σ(n) rn ), h1 = (σ(n) rn+1 , ..., σ(n) 2rn ), h2 = (σ(n) 2rn+1 , ..., σ(n) 3rn ),..., where σ(n) i is the i-th largest mode-n singular value. From the definition of HOSVD and Lemma 2, we have

Due to the mean-inequation, one has ‖hi‖22 ≥ ‖hi‖21 /rn, (i = 0, 1, ...). Assume that ‖h1‖1 = t(∑i≥1 ‖hi‖1) with some t ∈ [0, 1]. Then we have (∑i≥2 ‖hi‖1) = (1 - t)(∑i≥1 ‖hi‖1).

First from Lemma 2.1, Lemma 2.2 in [Mo and Li, 2011] and (22) we have

and

From (25) we have

So we have

and

Further more, by (24),(26) we have

Since F(H0 + H1 + H2...) = F(H) = 0, we have ‖F(H0 + H1))‖22 = ‖F(H2 +H3 + ...))‖22 , by the above equations we have

Hence, let δ = δ(I1,I2,...,2rn,...,IN)

We have a quadratic polynomial of t with t ∈ [0, 1] in the right-hand side of the above inequality. Hence, by calculus, this quadratic polynomial achieves its maximal value at t = 1-3δ/2 4-25δ/8 ∈ [0, 1]. Therefore we obtain ‖h0‖1 ≤ θ( ∑ i≥1 ‖hi‖1),

where

δ < (77-√1337)/82 ≈ 0.4931, then θ < 1, we get ‖h0‖1 < ( ∑ i≥1 ‖hi‖1), which is

If for all n = (1, ...,N), we have (33), then we get (15).

Proof of Theorem 9.

Proof. The proof of Theorem 8 establishes that any nonzero H ∈ Null(F) satisfies ‖h0‖1 ≤ θ( ∑ i≥1 ‖hi‖1). Hence, if (1 +

For δ = 0.0.4404, we obtain (θ-1 - 1)-1 ‖X0 (i) ‖2 ≈ 9.9849‖X0 (i) ‖2 ≤ α, which proves the theorem.

Proof of Theorem 10.

Proof. Condition (16) is equivalent to

Since ri∑

j=1

σj(H(i)) ≤ √ri√ ri∑

√ri‖H(i)‖F , (35) holds provide that

Now from (18) and (19), one has

which is equivalent to

Thus the null-space condition holds.

Acknowledgments

The authors would like to thank the anonymous reviewers for their comments. This work was partly supported by the National Natural Science Foundation of China under grant No. 91120303 and No. 61071181.

σj(H(i))2 ≤

j=1