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

2020
Views:

429

Pages:

23
Author:

D Robbins

Pn no DSVD Suppose that Pn has a DSVD with singular values λ1 , . . . , λr . P kPn k? = nn/2 = ri=1 λi kPn kσ = n! nn/2 = λ1 P kPn k2 = n! = ri=1 λ2i λ1 r X λi = n! = i=1 so λ1 = · · · = λr , and r = rλλ11 = If n > 2 then r is not an integer! r X λ2i i=1 kDn k? kDn kσ = nn n! . Tensors Decompositions and the Nuclear Norm Noisy Signal Model Suppose that V is a finite dimensional R-vector space of signals. If c ∈ V is a noisy signal, then there is a decomposition c =a+b where a ∈ V is a sparse original signal, and b ∈ V is additive noise. Using convex relaxation, sparsity is measured by some `1 -type norm k · kX . The noise is measured by some `2 -type norm k · kY . Tensors Decompositions and the Nuclear Norm Noisy Signal Model Suppose that V is a finite dimensional R-vector space of signals. If c ∈ V is a noisy signal, then there is a decomposition c =a+b where a ∈ V is a sparse original signal, and b ∈ V is additive noise. Using convex relaxation, sparsity is measured by some `1 -type norm k · kX . The noise is measured by some `2 -type norm k · kY . For example, c is a tensor in V = V (1) ⊗ · · · ⊗ V (d) , k · kX = k · k? is the nuclear norm, and k · kY = k · k2 = k · k is the usual `2 -norm. (see the CoDe Model) Tensors Decompositions and the Nuclear Norm The Pareto Frontier V finite dimensional R-vector space k · kX , k · kY norms on V c ∈V Definition A pair (x, y ) ∈ R2 is Pareto-efficient if there exists a decomposition c = a + b with kak = x, kbk = y and for every decomposition c = a0 + b 0 we have ka0 kX > x, kb 0 kY > y or (ka0 kX , kb 0 kY ) = (x, y ). We call c = a + b an XY -decomposition. The Pareto-frontier consists of all Pareto-efficient pairs. Tensors Decompositions and the Nuclear Norm The Pareto Frontier V finite dimensional R-vector space k · kX , k · kY norms on V c ∈V Definition A pair (x, y ) ∈ R2 is Pareto-efficient if there exists a decomposition c = a + b with kak = x, kbk = y and for every decomposition c = a0 + b 0 we have ka0 kX > x, kb 0 kY > y or (ka0 kX , kb 0 kY ) = (x, y ). We call c = a + b an XY -decomposition. The Pareto-frontier consists of all Pareto-efficient pairs. Lemma The Pareto-frontier is the graph of a strictly decreasing, convex, c : [0, kck ] → [0, kck ]. homeomorphism fYX X Y Tensors Decompositions and the Nuclear Norm The Pareto Sub-Frontier h·, ·i positive definite p bilinear form kv k2 := kv k = hv , v i `2 -norm k · kX , k · kY dual to each others Tensors Decompositions and the Nuclear Norm The Pareto Sub-Frontier h·, ·i positive definite p bilinear form kv k2 := kv k = hv , v i `2 -norm k · kX , k · kY dual to each others Theorem Equivalent: 1. c = a + b is an X 2-decomposition 2. c = a + b is an 2Y -decomposition 3. ha, bi = kakX kbkY . Tensors Decompositions and the Nuclear Norm The Pareto Sub-Frontier h·, ·i positive definite p bilinear form kv k2 := kv k = hv , v i `2 -norm k · kX , k · kY dual to each others Theorem Equivalent: 1. c = a + b is an X 2-decomposition 2. c = a + b is an 2Y -decomposition 3. ha, bi = kakX kbkY . Definition The Pareto sub-frontier consists of all pairs (x, y ) such that there exists an X 2-decomposition c = a + b with kakX = x and kbkY = y . Tensors Decompositions and the Nuclear Norm The Pareto Sub-Frontier Lemma The Pareto sub-frontier is the graph of a strictly decreasing c : [0, kck ] → [0, kck ]. homeomorphism hYX X Y c ≤ hc . Clearly, fYX YX Definition c = hc . If all vectors in V are A vector c ∈ V is called tight if fYX YX tight then the norms k · kX and k · kY are called tight. Tensors Decompositions and the Nuclear Norm (Sub)-Pareto Example c = (3 3)t ∈ V = R2 q z1 = 12 z12 + 2z22 , z2 X z1 z2 = q 2z12 + 12 z22 . Y dual norms fYX,hYX 5 4 3 2 1 0 0 1 2 3 4 5 So c is not tight. Tensors Decompositions and the Nuclear Norm The Area Below the Pareto Sub-Frontier Suppose c = a + b is an X 2-decomposition with kakX = x0 and kbkY = y0 . The area under the Pareto sub-frontier is 1 1 1 2 2 2 2 kck = 2 kak + ha, bi + 2 kbk . hYX Y ||c||Y (1/2)||a||22 (||a|| ,||b|| ) X y Y 0 (1/2)||b||22 X x0 Harm Derksen ||c||X Tensors Decompositions and the Nuclear Norm The Area Below the Pareto Sub-Frontier The sub-Pareto frontier applies to: I denoising a sparse 1D signal: k · k1 vs. k · k∞ (tight!) I denoising of a matrix by soft tresholding: k · k? vs.k · kσ (tight!) I denoising tensors: k · k? vs. k · kσ I compressive sensing (Basis Pursuit Denoising, LASSO, Dantzig Selector) I Fatemi-Osher-Rudin image denoising: total variation norm vs. its dual I 1D total variation denoising: Taut String Method Harm Derksen Tensors Decompositions and the Nuclear Norm Example: Singular Value Decomposition Rn×m = Rn ⊗ Rm , r = min{n, m} A ∈ Rn×m with singular values λ1 ≥ λ2 ≥ · · · ≥ λr ≥ 0 kAkX = kAk? = λ1 + λ2 + · · · + λr kAkY = kAkσ = λ1 q kAk = λ21 + λ22 + · · · + λ2r Harm Derksen Tensors Decompositions and the Nuclear Norm Example: Singular Value Decomposition Rn×m = Rn ⊗ Rm , r = min{n, m} A ∈ Rn×m with singular values λ1 ≥ λ2 ≥ · · · ≥ λr ≥ 0 kAkX = kAk? = λ1 + λ2 + · · · + λr kAkY = kAkσ = λ1 q kAk = λ21 + λ22 + · · · + λ2r Lemma The norms k · k? and k · kσ are tight. XY -decompositions are related to soft tresholding Harm Derksen Tensors Decompositions and the Nuclear Norm Example: Singular Value Decomposition (note that the Pareto and sub-Pareto frontiers are the same here) Lemma If A has singular values λ1 ≥ λ2 ≥ · · · ≥ λr ≥ 0 then the Pareto (sub-)frontier is the piecewise linear function through the points: (λ1 + λ2 + · · · + λk − kλk+1 , λk+1 ), k = 0, 1, 2, . . . , r (with the convention λr +1 = 0). Harm Derksen Tensors Decompositions and the Nuclear Norm Example: Singular Value Decomposition (note that the Pareto and sub-Pareto frontiers are the same here) Lemma If A has singular values λ1 ≥ λ2 ≥ · · · ≥ λr ≥ 0 then the Pareto (sub-)frontier is the piecewise linear function through the points: (λ1 + λ2 + · · · + λk − kλk+1 , λk+1 ), k = 0, 1, 2, . . . , r (with the convention λr +1 = 0). Corollary The singular values are uniquely determined by the (sub-)Pareto curve, and vice versa. Harm Derksen Tensors Decompositions and the Nuclear Norm Slope decomposition Definition c = c1 + c2 + · · · + cs is called a slope decomposition if hci , cj i = kci kX kcj kY for all i ≤ j and kc1 kX kc2 kX kcr kX < < ··· < . kc1 kY kc2 kY kcr kY Harm Derksen Tensors Decompositions and the Nuclear Norm Slope decomposition Definition c = c1 + c2 + · · · + cs is called a slope decomposition if hci , cj i = kci kX kcj kY for all i ≤ j and kc1 kX kc2 kX kcr kX < < ··· < . kc1 kY kc2 kY kcr kY Theorem c ∈ V has a slope decomposition if and only if c is tight. Harm Derksen Tensors Decompositions and the Nuclear Norm Slope decomposition Definition c = c1 + c2 + · · · + cs is called a slope decomposition if hci , cj i = kci kX kcj kY for all i ≤ j and kc1 kX kc2 kX kcr kX < < ··· < . kc1 kY kc2 kY kcr kY Theorem c ∈ V has a slope decomposition if and only if c is tight. Theorem The slope decomposition is unique when it exists. Harm Derksen Tensors Decompositions and the Nuclear Norm Singular values for tight vectors Suppose c ∈ V is tight, with slope decomposition c = c1 + c2 + · · · + cs . Definition Let µi = kci kY , and λi = µi + µi+1 + · · · + µs for all i. Then c kci−1 kX kci kX has singular value λi with multiplicity kc − kci−1 kY . i kY Multiplicities and singular values are positive, but not necessarily integers. Harm Derksen Tensors Decompositions and the Nuclear Norm Singular values for tight vectors Suppose c ∈ V is tight, with slope decomposition c = c1 + c2 + · · · + cs . Definition Let µi = kci kY , and λi = µi + µi+1 + · · · + µs for all i. Then c kci−1 kX kci kX has singular value λi with multiplicity kc − kci−1 kY . i kY Multiplicities and singular values are positive, but not necessarily integers. Theorem If c has singular Values λ1P , . . . , λs with multiplicities m1 , . . . , ms respectively, then kck = X i mi λi , kckY = λ1 and qP 2 kT k = i mi λi . Harm Derksen Tensors Decompositions and the Nuclear Norm Singular Values for Tensors Norms k · kX = k · k? , k · kY = k · kσ Theorem P If T = ri=1 λi vi is a diagonal singular value decomposition, then the singular values of T are λ1 , . . . , λr . Harm Derksen Tensors Decompositions and the Nuclear Norm Singular Values for Tensors Norms k · kX = k · k? , k · kY = k · kσ Theorem P If T = ri=1 λi vi is a diagonal singular value decomposition, then the singular values of T are λ1 , . . . , λr . The permanent tensor Pn is tight, but has no DSVD. nn It has singular value nn! n/2 with multiplicity n! . Harm Derksen Tensors Decompositions and the Nuclear Norm

Tensors Decompositions and the Nuclear Norm-3

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock