University:
University of Michigan
Course:
MATH 217 | Linear Algebra
Academic year:

2022
Views:

87

Pages:

16
Author:

CBlair

Tensors Decompositions and the Nuclear Norm Harm Derksen Tensors Decompositions and the Nuclear Norm Tensor Rank F a field, F = R or F = C V (i) ∼ = Fni for i = 1, 2, . . . , d V = V (1) ⊗ V (2) ⊗ · · · ⊗ V (d) ∼ = Fn1 ×···×nd tensor product space Definition A pure tensor is a tensor of the form v (1) ⊗ v (2) ⊗ · · · ⊗ v (d) (v (i) ∈ V (i) ). Harm Derksen Tensors Decompositions and the Nuclear Norm Tensor Rank F a field, F = R or F = C V (i) ∼ = Fni for i = 1, 2, . . . , d V = V (1) ⊗ V (2) ⊗ · · · ⊗ V (d) ∼ = Fn1 ×···×nd tensor product space Definition A pure tensor is a tensor of the form v (1) ⊗ v (2) ⊗ · · · ⊗ v (d) (v (i) ∈ V (i) ). Definition (tensor rank) The rank of T is the smallest positive integer r such that T is the sum of r pure tensors. Tensors Decompositions and the Nuclear Norm The Canonical Polyadic (CP) Model aka PARAFAC, CANDECOMP Problem Given a tensor T ∈ V , write T = v1 + v2 + · · · + vr where v1 , v2 , . . . , vr are pure tensors and r is minimal. Tensors Decompositions and the Nuclear Norm The Canonical Polyadic (CP) Model aka PARAFAC, CANDECOMP Problem Given a tensor T ∈ V , write T = v1 + v2 + · · · + vr where v1 , v2 , . . . , vr are pure tensors and r is minimal. I the CP-decomposition may not be unique I not numerically stable: there is no upper bound for max{kv1 k, . . . , kvr k} as a function of kT k. I difficult to compute: for many tensors of interest the rank is unknown To make it more numerically stable, we could allow an error term. Tensors Decompositions and the Nuclear Norm The Canonical Polyadic (CP) Model Problem Given a tensor T ∈ V and fixed r , write T = v1 + v2 + · · · + vr + E where v1 , v2 , . . . , vr are pure tensors and kE k is minimal. Tensors Decompositions and the Nuclear Norm The Canonical Polyadic (CP) Model Problem Given a tensor T ∈ V and fixed r , write T = v1 + v2 + · · · + vr + E where v1 , v2 , . . . , vr are pure tensors and kE k is minimal. This optimization problem might be ill-posed. Define T = e2 ⊗ e1 ⊗ e1 + e1 ⊗ e2 ⊗ e 1 + e 1 ⊗ e 1 ⊗ e 2 , v1 (t) = t −1 (e1 +te2 )⊗(e1 +te2 )⊗(e1 +te2 ), v2 (t) = −t −1 e1 ⊗e1 ⊗e1 √ Then T = v1 (t) + v2 (t) + E (t) with kE (t)k = t 3 + t. So we can write T = v1 + v2 + E with kE k = ε for every ε > 0, but we cannot write T = v1 + v2 + E with kE k = 0. Tensors Decompositions and the Nuclear Norm Motivation: Compressed Sensing and Convex Relaxation For x ∈ Rn , its sparsity is measured by kxk0 = #{i | xi 6= 0}. Problem Given A ∈ Matm,n (R), b ∈ Rm , find a solution x ∈ Rn for Ax = b with kxk0 minimal (a sparsest solution). But, k · k0 is not convex and this optimization problem is difficult, Tensors Decompositions and the Nuclear Norm Motivation: Compressed Sensing and Convex Relaxation For x ∈ Rn , its sparsity is measured by kxk0 = #{i | xi 6= 0}. Problem Given A ∈ Matm,n (R), b ∈ Rm , find a solution x ∈ Rn for Ax = b with kxk0 minimal (a sparsest solution). But, k · k0 is not convex and this optimization problem is difficult, so instead we consider: Problem (Basis Pursuit) Given A ∈ Matm,n (R), b ∈ Rm , find a solution x ∈ Rn for Ax = b with kxk1 minimal. Basis Pursuit can be solved by linear programming and is generally fast. Under reasonable assumptions, Basis Pursuit also gives the sparsest solutions (Candès-Tao, Donoho). Tensors Decompositions and the Nuclear Norm The Nuclear and Spectral Norms Low rank tensors are sparse in some sense, and by convex relaxation: Definition Pr The nuclear norm kT k is the smallest value of ? i=1 kvi k where Pr T = i=1 vi and v1 , . . . , vr are pure tensors. (well-defined) Tensors Decompositions and the Nuclear Norm The Nuclear and Spectral Norms Low rank tensors are sparse in some sense, and by convex relaxation: Definition Pr The nuclear norm kT k is the smallest value of ? i=1 kvi k where Pr T = i=1 vi and v1 , . . . , vr are pure tensors. (well-defined) V (1) , . . . , V (d) , V a spaces with a positive definite bilinear/hermitian form h·, ·i Tensors Decompositions and the Nuclear Norm The Nuclear and Spectral Norms Low rank tensors are sparse in some sense, and by convex relaxation: Definition Pr The nuclear norm kT k is the smallest value of ? i=1 kvi k where Pr T = i=1 vi and v1 , . . . , vr are pure tensors. (well-defined) V (1) , . . . , V (d) , V a spaces with a positive definite bilinear/hermitian form h·, ·i Definition The spectral norm is defined by kT kσ = max{|hT , v i| | v pure tensor with kv k = 1}. The spectral norm is dual to the nuclear norm, in particular |hT , Si| ≤ kT k? kSkσ for all tensors S, T . Tensors Decompositions and the Nuclear Norm Example: Permanent Tensor Pn = P σ∈Sn eσ(1) ⊗ eσ(2) ⊗ · · · ⊗ eσ(n) ∈ Cn ⊗ · · · ⊗ Cn . kPn kσ = max{| perm(v1 v2 · · · vn )| | kv1 k = · · · = kvn k = 1} Tensors Decompositions and the Nuclear Norm Example: Permanent Tensor Pn = P σ∈Sn eσ(1) ⊗ eσ(2) ⊗ · · · ⊗ eσ(n) ∈ Cn ⊗ · · · ⊗ Cn . kPn kσ = max{| perm(v1 v2 · · · vn )| | kv1 k = · · · = kvn k = 1} Theorem (Carlen, Lieb and Moss, 2006) max{perm(v1 v2 · · · vn ) | kv1 k = · · · = kvn k = 1} = n!/nn/2 kPn k? = nn/2 nn/2 kPn k? kPn kσ ≥ hPn , Pn i = nn/2 . n! n! Tensors Decompositions and the Nuclear Norm Example: Permanent Tensor Theorem (Glynn 2010) Pn = 1 2n−1 X Qn P Pn n δ i=1 i ( i=1 δi ei ) ⊗ · · · ⊗ ( i=1 δi ei ) δ where δ runs over {1} × {−1, 1}n−1 . Tensors Decompositions and the Nuclear Norm Example: Permanent Tensor Theorem (Glynn 2010) Pn = 1 2n−1 X Qn P Pn n δ i=1 i ( i=1 δi ei ) ⊗ · · · ⊗ ( i=1 δi ei ) δ where δ runs over {1} × {−1, 1}n−1 . n ≤ rank(Pn ) ≤ 2n−1 and kPn k? ≤ nn/2 , so In particular, bn/2c Theorem (D.) kPn k? = nn/2 Tensors Decompositions and the Nuclear Norm

Tensors Decompositions and the Nuclear Norm-1

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock