3.5K Views
August 24, 21
スライド概要
電子情報通信学会 信号処理研究会(2021/08/24)
開催プログラム:https://www.ieice.org/ken/program/index.php?tgs_regid=cb0654c999afe7fe2e1a821190ed08bd383d6b9b1ded7f62427b2789f35687e7&tgid=IEICE-SIP
東京農工大学大学院工学研究院 准教授
20 2 1/ 08/24 ৴ ߸ॲཧ ڀ ݚձ ઢ ٯ ܗ ʹର͢Δತ࠷దԽͷ ಛ ੑ ղ ੳͱͦͷԠ༻ େ ࡕେֶ େ ֶ Ӄ ڀ ݚ ֶ ૅ جՊ ૣྒ
࣍ ✦ ઢ ٯܗ ʹର͢Δತ࠷దԽ ✦ $ (.5Λ༻͍ͨཧղੳ ✦ $ (.5Λ༻͍ͨཧղੳͷԠ༻ ✦ ❖ ະͷࡶԻࢄͷਪఆ ❖ ࠷దԽΞϧΰϦζϜͷղੳ ࠓ ޙͷలɾ·ͱΊ
࣍ ✦ ઢ ٯܗ ʹର͢Δತ࠷దԽ ✦ $ (.5Λ༻͍ͨཧղੳ ✦ $ (.5Λ༻͍ͨཧղੳͷԠ༻ ✦ ❖ ະͷࡶԻࢄͷਪఆ ❖ ࠷దԽΞϧΰϦζϜͷղੳ ࠓ ޙͷలɾ·ͱΊ
ઢٯܗʹର͢Δತ࠷దԽ 1/34 ઢٯܗ ✓ ະ ϕΫτϧ x ∈ ℝN Λ ͦͷઢ ؍ ܗଌ y = Ax + v ∈ ℝM ͔Βਪఆ N M y = A x + v ࡶԻ ਪ ఆ x̂ ྫɿ ✦ ૹ৴ ৴߸ ਪఆʢແ ઢ௨৴ ʣ ✦ ը૾ ෮ݩ ʢը ૾ॲ ཧʣ ✦ ઢܗճؼʢػց ֶशʣ
ઢٯܗʹର͢Δತ࠷దԽ 2/34 ѹ ॖηϯγϯά < > ✓ εύʔεͳʢ ྵ ͕ଟ͍ʣະϕΫτϧ x ∈ ℝN Λ ͦͷઢ ؍ ܗଌ y = Ax + v ∈ ℝM ͔Βਪఆ N M y = A ඇྵ x + v ࡶԻ ਪ ఆ x̂ ྫɿ ✦ .3 *ը ૾࠶ ߏ < > ʢ.BHOFUJ D3 FTPOBOD F*N BHJOHʣ ✦ ແઢ ௨৴ ࿏ਪ ఆ < > [1] D. L. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1289–1306, Apr. 2006. [2] M. Lustig, D. L. Donoho, J. M. Santos, and J. M. Pauly, “Compressed sensing MRI,” IEEE Signal Process. Mag., vol. 25, no. 2, pp. 72–82, Mar. 2008. [3] K. Hayashi, M. Nagahara, and T. Tanaka, “A user’s guide to compressed sensing for communications systems,” IEICE Trans. Commun., vol. E96-B, no. 3, pp. 685–712, Mar. 2013.
ઢٯܗʹର͢Δತ࠷దԽ
ѹ ॖηϯγϯάͷΞϧΰϦζϜ
✓
3/34
ѹ ॖηϯγϯάʹର͢Δ༷ʑͳख ๏͕ఏҊ͞Ε͍ͯΔ
✦
ᩦཉ๏ɿඇྵ ͷॴΛॱ ൪ʹਪ ఆ
❖
❖
✦
0 .1ʢ0SU IPHPOBM. 1ʣ< > ͳͲ
ϝοηʔδ๏ɿ֬ʢ ৴ ೦ ʣ ๏ͷۙࣅ
❖
✦
. 1ʢ.BUDI JOH1VSTVJUʣ< >
". 1ʢ"QQSPYJNBU F.FTTBHF1BTTJOHʣ< > ͳͲ
࠷దԽɿతؔ ͷ࠷খ Խ
❖
❖
* 45 "ʢ* UF SBUJWF4PGU 5ISFTIPME JOH"M HPSJUIN ʣ< >
' *45"ʢ'BTU*45"ʣ< > ͳͲ
[4] S. Mallat and Z. Zhang, “Matching pursuits with time-frequency dictionaries,” IEEE Trans. Signal Process., vol. 41,
no. 12, pp. 3397–3415, Dec. 1993.
[5] J. A. Tropp and A. C. Gilbert, “Signal recovery from random measurements via orthogonal matching pursuit,”
IEEE Trans. Inf. Theory, vol. 53, no. 12, pp. 4655–4666, Dec. 2007.
[6] D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algorithms for compressed sensing,” PNAS, vol. 106,
no. 45, pp. 18914–18919, Nov. 2009.
[7] I. Daubechies, M. Defrise, and C. D. Mol, “An iterative thresholding algorithm for linear inverse problems with a
sparsity constraint,” Commun. Pure Appl. Math., vol. 57, no. 11, pp. 1413–1457, 2004.
[8] A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” SIAM J.
Imaging Sci., vol. 2, no. 1, pp. 183–202, Jan. 2009.
ઢٯܗʹର͢Δತ࠷దԽ 4/34 ࠷ ద Խʹ ํͮ͘ج๏ ✓ ٻΊ͍ͨͷʢ x ʣʹର͢Δ͕খ͘͞ͳΔΑ͏ͳత ؔ Λ࠷ খ Խ ύϥϝʔλ 1 ∥y − As∥22 + λ f(s) جຊతͳܗɿ x̂ = arg min {2 } s∈ℝN y = Ax + v ਖ਼ଇ Խ߲ɿ x ʹؔ͢Δࣄ લ ใΛ༻׆ 1 ∥y − As∥22 + λ f(s) 2 x x̂ s
ઢٯܗʹର͢Δತ࠷దԽ 5/34 ℓ1ਖ਼ ଇ ԽΛ༻͍ͨεύʔεϕΫτϧͷਪఆ N ✓ f(s) = ∥s∥ ℓ1 ਖ਼ ଇ Խ 1= ∑ |s n| ʢ snɿ s ͷୈ n ʣΛ༻͍ͨ n=1 ࠷ద Խ Λղ͘ͱɼεύʔεͳʢྵ ͕ଟ͍ʣਪఆΛಘΒΕΔ N M y = A x + v ࡶԻ ඇ ྵ 1 ∥y − As∥22 + λ ∥s∥1 ਪ ఆ x̂ = arg min {2 } s∈ℝN
࣍ ✦ ઢ ٯܗ ʹର͢Δತ࠷దԽ ✦ $ (.5Λ༻͍ͨཧղੳ ✦ $ (.5Λ༻͍ͨཧղੳͷԠ༻ ✦ ❖ ະͷࡶԻࢄͷਪఆ ❖ ࠷దԽΞϧΰϦζϜͷղੳ ࠓ ޙͷలɾ·ͱΊ
$(.5Λ༻͍ͨཧղੳ
ਪ ఆ ͷࠩ ޡͷղ ੳ
✓
1
ਪ ఆ
∥y
− As∥
22 +
λ f(s)
ͷࠩޡΛΓ͍ͨ
x̂ = argmin
{2
}
s∈ℝN
ղੳͷΞϓϩʔν
✦
1
ྫɿ.4 &ʢ. F BO 4RVB SF E&SSPSʣ ∥x̂ − x∥22
N
ϝοηʔδ ๏ʹͮ͘جղ ੳ < >
❖
✦
6/34
ϝοηʔδ ๏ͷಛ ੑΛղ ੳ ˠ ࠷ దԽͱͷؔΛٞ
$( . 5ʢ$POWFY(B VTTJBO.JONB Y 5IFP SFNʣʹͮ͘جղ ੳ < >
❖
࠷ ద Խ Λগ͠ม ͨ͠ܗͷΛղ ੳ
[9] D. L. Donoho, A. Maleki, and A. Montanari, “The noise-sensitivity phase transition in compressed sensing,”
IEEE Trans. Inf. Theory, vol. 57, no. 11, pp. 6920–6941, Oct. 2011.
[10] M. Bayati and A. Montanari, “The LASSO risk for Gaussian matrices,” IEEE Trans. Inf. Theory, vol. 58, no. 4,
pp. 1997–2017, Apr. 2012.
[11] C. Thrampoulidis, S. Oymak, and B. Hassibi, “Regularized linear regression: A precise analysis of the estimation error,”
in Proc. COLT, Jun. 2015, pp. 1683–1709.
[12] C. Thrampoulidis, E. Abbasi, and B. Hassibi, “Precise error analysis of regularized M-estimators in high dimensions,”
IEEE Trans. Inf. Theory, vol. 64, no. 8, pp. 5592–5628, Aug. 2018.
$(.5Λ༻͍ͨཧղੳ 7/34 ղ ੳʹ͓͚ΔԾఆ ؍ଌ Δ = M/N ͕ҰఆͰ M, N → ∞ͱͳΔݶۃΛߟ͑Δ ֤ ಠ ཱʹ֬ pX ʹै͏ N M y = A x + v ֤ಠཱʹ ฏ ۉ0ɾࢄ σv2 ͷ Ψεʹै͏ ֤ಠཱʹ ฏ ۉ0ɾࢄ 1/N ͷΨεʹै͏ 1 ਪఆ x̂ = arg min ∥y − As∥22 + λ f(s) ( f(s) = ∥s∥1 ) {2 } s∈ℝN
$(.5Λ༻͍ͨཧղੳ 8/34 $( . 5ʢͷΠϝʔδʣ ✓ ओ ʢ 1 SJ N BS Z 0 Q U JN J[B UJ PO 10ʣͱ ิ ॿ ʢ " V YJM J B S Z 0 Q U JN J[B UJ PO "0ʣΛؔ࿈͚Δఆཧ ʢ10ʣ ʢ" 0ʣ min max { u 𝖳Ge + ξ(e, u)} min max {∥e∥2 g 𝖳u − ∥u∥2 h 𝖳e + ξ(e, u)} e∈𝒮e u∈𝒮u e∈𝒮e u∈𝒮u 𝒮 𝒮 ϕ̄𝒮c ̂ eΦ e ̂ ∈ 𝒮) = 1 lim Pr (eΦ M, N→∞ ϕ̄ eϕ̂ e ݅ɿ M, N → ∞Ͱ ϕ̄ < ϕ̄𝒮c ʢ࠷ దղ͕ू߹ 𝒮 ʹଐ͢Δʣ
$(.5Λ༻͍ͨཧղੳ
8/34
$( . 5ʢͷΠϝʔδʣ
ξ : ℝN × ℝM → ℝɿ
eʹؔͯ͠ತؔ ɼ
✓ ओ
ʢ 1 SJMN BS Z 0 Q U JN J[B UJ PO 10ʣͱ uʹؔͯ͠Ԝؔ
N
𝒮e ⊂ ℝ , 𝒮u ⊂ ℝ ɿίϯύΫτू߹
ิ ॿ ʢ " V YJM J B S Z 0 Q U JN J[B UJ PO "0ʣΛؔ࿈͚Δఆཧ
G ∈ ℝM×N, g ∈ ℝM, h ∈ ℝNɿ֤͕ಠཱʹඪ४Ψε
ʢ10ʣ
ʢ" 0ʣ
min max { u 𝖳Ge + ξ(e, u)}
e∈𝒮e u∈𝒮u
min max {∥e∥2 g 𝖳u − ∥u∥2 h 𝖳e + ξ(e, u)}
e∈𝒮e u∈𝒮u
𝒮
𝒮
ϕ̄𝒮c
̂
eΦ
e
̂ ∈ 𝒮) = 1
lim Pr (eΦ
M, N→∞
ϕ̄
eϕ̂
e
݅ɿ M, N → ∞Ͱ ϕ̄ < ϕ̄𝒮c
ʢ࠷ దղ͕ू߹ 𝒮 ʹଐ͢Δʣ
$(.5Λ༻͍ͨཧղੳ
8/34
$( . 5ʢͷΠϝʔδʣ
ξ : ℝN × ℝM → ℝɿ
eʹؔͯ͠ತؔ ɼ
✓ ओ
ʢ 1 SJMN BS Z 0 Q U JN J[B UJ PO 10ʣͱ uʹؔͯ͠Ԝؔ
N
𝒮e ⊂ ℝ , 𝒮u ⊂ ℝ ɿίϯύΫτू߹
ิ ॿ ʢ " V YJM J B S Z 0 Q U JN J[B UJ PO "0ʣΛؔ࿈͚Δఆཧ
G ∈ ℝM×N, g ∈ ℝM, h ∈ ℝNɿ֤͕ಠཱʹඪ४Ψε
ʢ10ʣ
ʢ" 0ʣ
min max { u 𝖳Ge + ξ(e, u)}
e∈𝒮e u∈𝒮u
min max {∥e∥2 g 𝖳u − ∥u∥2 h 𝖳e + ξ(e, u)}
e∈𝒮e u∈𝒮u
𝒮
ײతʹʜ
𝒮
ิ ॿ ʢ" 0 ʣͷղ͕ߴ ֬ Ͱू߹ 𝒮 ʹଐ͢Δ
ˠ ओ ʢ 10 ʣͷղߴ ֬ Ͱू߹ 𝒮 ʹଐ͢Δ
ϕ̄𝒮c
ϕ̄
ओ ʢ 10 ʣͷΘΓʹิ ॿ ʢ "0 ʣΛղੳͯ͠Α͍
e
̂
̂
eΦ
e
̂ ∈ 𝒮) = 1
lim Pr (eΦ
M, N→∞
eϕ
݅ɿ M, N → ∞Ͱ ϕ̄ < ϕ̄𝒮c
ʢ࠷ దղ͕ू߹ 𝒮 ʹଐ͢Δʣ
$(.5Λ༻͍ͨཧղੳ 9/34 $( . 5Λ༻͍ͨղੳʛ֓ཁ ✓ 1 2 ̂ ∥ x − x∥ $(. 5Λ༻͍ͯਪ ఆͷ. 4 & 2Λղੳ͢Δखॱ N 1 ݩͷ࠷ద Խ min 2 λ f(s) ∥y − As∥ + 2 ʢղ ੳͷର ʣ s∈ℝN { 2 } ओ ʢ 1 0 ʣͷʹܗมܗ ओ ʢ 10 ʣͷ ղੳ ݁Ռ ओ ʢ 1 0 ʣ ิ ॿ ʢ "0 ʣΛಋग़ ิॿ ʢ " 0 ʣ ݩͷ࠷ దԽ ͷ ղੳ݁Ռ ิ ॿ ʢ" 0 ʣΛղ ੳ $ (. 5 ิॿ ʢ"0 ʣͷ ղੳ ݁Ռ
$(.5Λ༻͍ͨཧղੳ 9/34 $( . 5Λ༻͍ͨղੳʛ֓ཁ ✓ 1 2 ̂ ∥ x − x∥ $(. 5Λ༻͍ͯਪ ఆͷ. 4 & 2Λղੳ͢Δखॱ N 1 ݩͷ࠷ద Խ min 2 λ f(s) ∥y − As∥ + 2 ʢղ ੳͷର ʣ s∈ℝN { 2 } ओ ʢ 1 0 ʣͷʹܗมܗ ओ ʢ 10 ʣͷ ղੳ ݁Ռ ओ ʢ 1 0 ʣ ิ ॿ ʢ "0 ʣΛಋग़ ิॿ ʢ " 0 ʣ ݩͷ࠷ దԽ ͷ ղੳ݁Ռ ิ ॿ ʢ" 0 ʣΛղ ੳ $ (. 5 ิॿ ʢ"0 ʣͷ ղੳ ݁Ռ
$(.5Λ༻͍ͨཧղੳ 10/34 $( . 5Λ༻͍ͨղੳʛʢ 10ʣͷมܗʢʣ ✓ ݩͷ࠷ద Խ Λओ ʢ 10 ͷʹܗม ܗ 1 minN ∥y − As∥22 + λ f(s) s∈ℝ { 2 } ࠩ ޡϕΫτϧ e := s − x ͷ࠷ద Խͱͯ͠දݱ 1 1 minN ∥Ae − v∥22 + λ f(x + e) e∈ℝ N { 2 } M, N → ∞ Ͱత ؔ ͕ൃࢄ͠ͳ͍Α͏ʹ 1/N ഒ
$(.5Λ༻͍ͨཧղੳ 11/34 $( . 5Λ༻͍ͨղੳʛʢ 10ʣͷมܗʢʣ ✓ ݩͷ࠷ద Խ Λओ ʢ 10 ͷʹܗม ܗ 1 1 minN ∥Ae − v∥22 + λ f(x + e) e∈ℝ N { 2 } D Gತ ڞͷࣜ ψ(z) = sup {u 𝖳 z − ψ*(u)} M u∈ℝ N 1 2 𝖳 ∥Ae − v∥2 = max Nu (Ae − v) − ∥u∥22 2 2 u∈ℝM { } Λͬͯม ܗ ʢ 10 ʣ ತڞ 1 𝖳 1 𝖳 1 minN max u ( NA) e − v u − ∥u∥22 + λ f(x + e) 2 e∈ℝ u∈ℝM { N } N
$(.5Λ༻͍ͨཧղੳ $( . 5Λ༻͍ͨղੳʛ֓ཁ ✓ 1 2 ̂ ∥ x − x∥ $(. 5Λ༻͍ͯਪ ఆͷ. 4 & 2Λղੳ͢Δखॱ N 1 ݩͷ࠷ద Խ min 2 λ f(s) ∥y − As∥ + 2 ʢղ ੳͷର ʣ s∈ℝN { 2 } ओ ʢ 1 0 ʣͷʹܗมܗ ओ ʢ 10 ʣͷ ղੳ ݁Ռ ओ ʢ 1 0 ʣ ิ ॿ ʢ "0 ʣΛಋग़ ิॿ ʢ " 0 ʣ ݩͷ࠷ దԽ ͷ ղੳ݁Ռ ิ ॿ ʢ" 0 ʣΛղ ੳ $ (. 5 ิॿ ʢ"0 ʣͷ ղੳ ݁Ռ
$(.5Λ༻͍ͨཧղੳ $( . 5Λ༻͍ͨղੳʛʢ "0ʣͷಋग़ ✓ 12/34 ओ ʢ 1 0 ʣʹର Ԡ͢Δิ ॿ ʢ "0 Λಋग़ min max { u 𝖳Ge + ξ(e, u)} e∈𝒮e u∈𝒮u min max {∥e∥2 g 𝖳u − ∥u∥2 h 𝖳e + ξ(e, u)} e∈𝒮e u∈𝒮u ʢ 10 ʣ 1 𝖳 1 𝖳 1 minN max u ( NA) e − v u − ∥u∥22 + λ f(x + e) 2 e∈ℝ u∈ℝM { N } N ʢ "0ʣ 1 1 𝖳 1 𝖳 𝖳 2 ∥e∥ g u − ∥u∥ h e minN max − v u − ∥u∥ ( 2 ) 2 2 + λ f(x + e) M 2 e∈ℝ u∈ℝ { N } N ˞ʹີݫɼ੍ ू߹ 𝒮e, 𝒮u ʹؔ͢Δٞඞ ཁ
$(.5Λ༻͍ͨཧղੳ $( . 5Λ༻͍ͨղੳʛ֓ཁ ✓ 1 2 ̂ ∥ x − x∥ $(. 5Λ༻͍ͯਪ ఆͷ. 4 & 2Λղੳ͢Δखॱ N 1 ݩͷ࠷ద Խ min 2 λ f(s) ∥y − As∥ + 2 ʢղ ੳͷର ʣ s∈ℝN { 2 } ओ ʢ 1 0 ʣͷʹܗมܗ ओ ʢ 10 ʣͷ ղੳ ݁Ռ ओ ʢ 1 0 ʣ ิ ॿ ʢ "0 ʣΛಋग़ ิॿ ʢ " 0 ʣ ݩͷ࠷ దԽ ͷ ղੳ݁Ռ ิ ॿ ʢ" 0 ʣΛղ ੳ $ (. 5 ิॿ ʢ"0 ʣͷ ղੳ ݁Ռ
$(.5Λ༻͍ͨཧղੳ $( . 5Λ༻͍ͨղੳʛʢ "0ʣͷมܗ ✓ 13/34 ิ ॿ ʢ " 0 Λม ܗ ʢ "0ʣ 1 1 𝖳 1 𝖳 𝖳 2 minN max ∥e∥ g u − ∥u∥ h e − v u − ∥u∥ + λ f(x + e) ( ) 2 2 2 2 e∈ℝ u∈ℝM { N } N తؔ Λ ཧͯ͠ M, N → ∞ ͱ͢Δʢ ৄࡉলུʣ min max α>0 β≥0 { αβ Δ 2 + σv2 β Δ 2α β2 αβ − − 2 2 Δ + pX ʹै͏֬ม ඪ४Ψεม E env αλ f X + β Δ ( α [ β Δ H Δ )]} α .P SF BVF OW F MP QF
$(.5Λ༻͍ͨཧղੳ $( . 5Λ༻͍ͨղੳʛʢ "0ʣͷղੳ ✓ 14/34 ิ ॿ ʢ " 0 ͷղΛղ ੳ min max α>0 β≥0 { αβ Δ 2 + σv2 β Δ 2α β2 αβ − − 2 2 Δ + pX ʹै͏֬ม ඪ४Ψεม E env αλ f X + β Δ ( α [ β Δ H Δ )]} α .P SF BVF OW F MP QF ✦ ˢͷղΛ (α*, β*) ̂ ✦ ิॿʢ"0ʣͷղΛe(AO) ͱ͓͘ M, N → ∞ Ͱ 1 P 2 ̂ ∥2 (α*)2 − σv2ʢ ∥e(AO) ֬ ऩ ଋʣ N ̂ = x̂ − x ʹ্ͷ݁ՌΛద༻ $(.5Λ༻͍ͯɼओʢ10 ͷղ e(PO)
$(.5Λ༻͍ͨཧղੳ $( . 5Λ༻͍ͨղੳʛ݁Ռ 15/34 f(s) =∥s∥ ℓ1 ਖ਼ଇ Խ Λ༻͍ͨ࠷ దԽ ͷղੳ݁Ռ 1 ✓ Ծ ఆɿ ✦ ✦ ؍ଌ ߦྻ A ∈ ℝM×N ͷ֤ ಠ ཱʹฏ ۉ0ɾࢄ 1/N ͷΨε ࡶ ԻϕΫτϧ v ∈ ℝM ͷ֤ ಠཱʹฏ ۉ0ɾࢄ σv2 ͷΨε ࠷ దԽ min max α>0 β≥0 { αβ Δ 2 + σv2 β Δ 2α β Δ β2 αβ α + E env αλ f X + H − − β Δ ( α 2 2 Δ Δ ) } ͕ͨͩ̍ͭͷղ (α*, β*) Λͭ 1 M, N → ∞Ͱ ∥x̂ − x∥22 N P (α*)2 − σv2ʢ ֬ऩଋʣ
$(.5Λ༻͍ͨཧղੳ $( . 5Λ༻͍ͨղੳʛ݁Ռ 15/34 f(s) =∥s∥ ℓ1 ਖ਼ଇ Խ Λ༻͍ͨ࠷ దԽ ͷղੳ݁Ռ 1 ✓ Ծ ఆɿ ؍ଌ ߦྻ A ∈ ℝM×N ͷ֤ ಠ ཱʹฏ ۉ0ɾࢄ 1/N ͷΨε (α, β) 2 M ͷ࠷ద Խ Λղ͘ͱɼ ✦ ࡶ ԻϕΫτϧ v ∈ ℝ ͷ֤ ಠཱʹฏ ۉ0ɾࢄ σv ͷΨε ਪ ఆ x̂ ͷۙత .4&͕·ٻΔ ࠷ దԽ ✦ min max α>0 β≥0 { αβ Δ 2 + σv2 β Δ 2α β Δ β2 αβ α + E env αλ f X + H − − β Δ ( α 2 2 Δ Δ ) } ͕ͨͩ̍ͭͷղ (α*, β*) Λͭ 1 M, N → ∞Ͱ ∥x̂ − x∥22 N P (α*)2 − σv2ʢ ֬ऩଋʣ
$(.5Λ༻͍ͨཧղੳ 16/34 γϛϡϨʔγϣϯ݅ ✓ ػࢉ ܭγϛϡϨʔγϣϯͰ ✦ ✦ 1 2 ̂ ∥ x − x∥ ࣮ ࡍʹਪ ఆΛߦͬͨͱ͖ͷ. 4 & 2 N 2 (α*) − σv2 ཧ ղ ੳ ݁ Ռ͔ΒಘΒΕΔۙ త.4 & ɹΛൺֱ ؍ଌ Δ = M/N = 0.6 M y = ֬ 0.9 Ͱ 0 ɼ֬ 0.1 Ͱඪ ४Ψε ʹै͏ N A x + v ࡶ Ի ࢄ σv2 = 0.001 1 ਪఆ x̂ = arg min ∥y − As∥22 + λ f(s) ( f(s) = ∥s∥1 ) {2 } s∈ℝN
$(.5Λ༻͍ͨཧղੳ 17/34 γϛϡϨʔγϣϯ݁Ռ N ͕े େ͖͍ ߹ɼ࣮ࡍͷ. 4 &ͱ ۙత.4&͕͍ۙͱͳΔ 10°1 empirical (N = 50) empirical (N = 100) empirical (N = 500) 10°2 ࣮ ࡍͷ.4 & empirical (N = 1000) prediction . 4& MSE ✓ ۙ త .4 & 10°3 λ = 0.02 ͕ۙྑ͍ύϥϝʔλͷ 10°4 0.02 0.04 0.06 ਖ਼ ଇԽύϥϝʔλ λ ∏ 0.08 0.10
$(.5Λ༻͍ͨཧղੳ $( . 5Λ༻͍ͨղੳʹؔ͢Δڀݚ ✦ ΑΓҰ ൠ తͳ࠷ ద Խ ͷ. 4 &ͷղੳ < > ✦ ࢄΛͱΔ৴ ߸ͷਪఆʹର͢Δ 18/34 4&3ʢ 4 ZNC P M &S SP S 3 BUF ʣͷղ ੳ < > ✦ ඇ ઢ ؍ ܗଌ͔Βͷਪ ఆͷԠ༻ < > ✦ ؍ଌߦ ྻͷ ใʹ·ؚ͕ࠩ ޡΕ͍ͯΔ߹ͷݕ౼ < > ✦ ෳ ૉ ྖ Ҭͷઢ ٯܗͷԠ༻ < > [12] C. Thrampoulidis, E. Abbasi, and B. Hassibi, “Precise error analysis of regularized M-estimators in high dimensions,” IEEE Trans. Inf. Theory, vol. 64, no. 8, pp. 5592–5628, Aug. 2018. [13] C. Thrampoulidis, W. Xu, and B. Hassibi, “Symbol error rate performance of box-relaxation decoders in massive MIMO,” IEEE Trans. Signal Process., vol. 66, no. 13, pp. 3377–3392, Jul. 2018. [14] R. Hayakawa and K. Hayashi, “Asymptotic performance of discrete-valued vector reconstruction via box-constrained optimization with sum of l1 regularizers,” IEEE Trans. Signal Process., vol. 68, pp. 4320–4335, 2020. [15] C. Thrampoulidis, E. Abbasi, and B. Hassibi, “LASSO with non-linear measurements is equivalent to one with linear measurements,” in Proc. NeurIPS, 2015, pp. 3420–3428. [16] A. M. Alrashdi, I. B. Atitallah, T. Y. Al-Naffouri, and M. Alouini, “Precise performance analysis of the LASSO under matrix uncertainties,” in Proc. IEEE GlobalSIP, Nov. 2017, pp. 1290–1294. [17] E. Abbasi, F. Salehi, and B. Hassibi, “Performance analysis of convex data detection in MIMO,” in Proc. IEEE ICASSP, May 2019, pp. 4554–4558.
࣍ ✦ ઢ ٯܗ ʹର͢Δತ࠷దԽ ✦ $ (.5Λ༻͍ͨཧղੳ ✦ $ (.5Λ༻͍ͨཧղੳͷԠ༻ ❖ ະͷࡶԻ ࢄͷਪఆ ❖ ࠷దԽΞϧΰϦζϜͷղੳ R . H a ya k a w a , “N o is e v ari anc e e s tim at ion u sin g asymp to ti c re sid ual ✦ ࠓ in cޙͷలɾ om p re s s e d ·ͱΊ s ens i n g ,” arXi v :2 0 09 .1 36 78 , Se p. 2 02 0.
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛະͷࡶԻࢄͷਪఆ ࡶ Ի ࢄͷਪఆ ✓ σv2 ͷେ͖͞ʹґଘ ਖ਼ ଇԽύϥϝʔλͷྑ͍ࡶԻࢄ λ ˠ ࡶ Ի ࢄ͕ະͷ ߹ʁ N M y = A ࡶԻ ࢄ σv2 Λਪఆ x + v ࡶ Ի ࢄ σv2 ͕ະ ਖ਼ଇ Խύϥϝʔλ λ Λܾ ఆ 1 ਪ ఆ x̂ = arg min ∥y − As∥22 + λ f(s) ( f(s) = ∥s∥1 ) {2 } s∈ℝN 19/34
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛະͷࡶԻࢄͷਪఆ
ۙ త ղ ੳʹͮ͘ج৴߸ରࡶԻൺͷਪఆ
✓
20/34
Ϧοδਖ਼ ଇԽΛ༻͍ͨ࠷ దԽͷ ۙత ղੳʹͮ͘ج
৴ ߸ର ࡶ Իൺͷਪ ఆ < >
ਖ਼ଇ Խύϥϝʔλ τ Λ ݻఆͨ͠ͱ͖ͷతؔͷ࠷ద
1
Θ(τ) = minN
∥y − As∥22 + τ ∥s∥22
s∈ℝ { 2
}
Ϧοδਖ਼ଇ Խ
ʹରͯ͠ɼM, N͕े େ͖͍ͱ͖
Θ(τ) ≈ θ1(τ) σx2 + θ2(τ) σv2
τ ͷؔ
ʢ ࢉ ܭՄ ೳʣ
x ͷ ͷࢄ
ෳͷ τ ʹؔ͢ΔࣜΛཱͯͯ
σx2, σv2ʹ͍ͭͯղ͘
✦ x ͷੑ ࣭ʢεύʔεੑͳͲʣΛ͍ͳ͖Ͱ༻׆
✦ M < Nͩͱਪఆ ਫ਼ ͕ྑ͘ͳ͍
[18] M. A. Suliman, A. M. Alrashdi, T. Ballal, and T. Y. Al-Naffouri, “SNR estimation in linear systems with Gaussian matrices,”
IEEE Signal Process. Lett., vol. 24, no. 12, pp. 1867–1871, Dec. 2017.
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛະͷࡶԻࢄͷਪఆ ۙ తͳࠩ ✓ 21/34 1 $(. 5Λ༻͍Δͱɼࠩ ∥y − A x∥ ̂ 22 ղੳՄೳ N 1 x̂ = arg min ∥y − As∥22 + λ f(s) {2 } s∈ℝN (α*, β*)ɿ min max α>0 β≥0 { αβ Δ 2 + σv2 β Δ 2α ( f(s) = ∥s∥1 ) β Δ β2 αβ α − − E env αλ f X + H + β Δ 2 α [ ( 2 Δ Δ )]} 1 P 2 (α*)2 − σv2ʢ ֬ऩଋʣ M, N → ∞Ͱ ∥x̂ − x∥2 N 1 2 P 2 ̂ 2 M, N → ∞Ͱ ∥y − A x∥ ֬ ऩଋʣ (β*) ʢ N σv2ͷใͳ͠Ͱ ࢉ ܭՄ ೳ σv2Λͬͯࢉ ܭ ͷղ
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛະͷࡶԻࢄͷਪఆ 22/34 ఏ Ҋ ࡶ Ի ࢄ ਪ ఆ๏ͷΞΠσΞ 10°3 N = 100 M = 90 λ = 0.001 empirical prediction 10°4 ࠩ residual ✓ 1 2 2 ࣮ ࡍͷ ࠩ ∥y − A x∥ ̂ 2 ͱۙ తͳ(β* ) Λൺֱͯ͠σv2 Λਪఆ N 10°5 10°6 10°7 °6 10 10°5 10°4 10°3 ࡶ Ի ࢄ σv2 æv2 10°2 10°1
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛະͷࡶԻࢄͷਪఆ 22/34 ఏ Ҋ ࡶ Ի ࢄ ਪ ఆ๏ͷΞΠσΞ ✓ 1 2 2 ࣮ ࡍͷ ࠩ ∥y − A x∥ ̂ 2 ͱۙ తͳ(β* ) Λൺֱͯ͠σv2 Λਪఆ N 10°3 ࠩ residual ᶃ ਖ਼ ଇ Խύϥϝʔλ λ Λݻఆ͠ɼ 1 °4 ̂ 22 Λࢉܭ ɹ ਪ ఆ x10̂ ΛٻΊͯࠩ ∥y − A x∥ N 10°5 σv2ʹґଘ 10°6 10°7 °6 10 10°5 N = 100 M = 90 λ = 0.001 empirical prediction ᶄ ༷ʑͳ σv2 ʹରͯ͠ 2 ɹ ۙతͳࠩ (β*) Λࢉܭ 1 2 2 ̂ 2 = (β*) ͱͳΔ σv2 Λ ᶅ ∥y − A x∥ N ɹ ࡶԻࢄͷਪ ఆͱ͢Δ °4 °3 °2 °1 10 10 ࡶ Ի ࢄ σv2 10 10 æv2 ˞ λ ͷઃఆͱ σv2 ͷਪఆΛ܁Γฦ͢͜ͱͰਪ ఆ ਫ਼ Λվ ળ Մ ೳ
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛະͷࡶԻࢄͷਪఆ 23/34 γϛϡϨʔγϣϯ݅ ✓ ػࢉ ܭγϛϡϨʔγϣϯͰɼະͷࡶ Իࢄͷਪఆਫ਼Λൺֱ /. 4 &ʢ /P S N B MJ [ F E .4 & ʣ 2 ̂ σ ( v − 2 2 σv ) 2 (σv2) ֬ 0.9 Ͱ 0 ɼ֬ 0.1 Ͱඪ४Ψε ʹै͏ N = 200 M = 160 M y = N A x + v ࡶ Ի ࢄ σv2 ∈ [10−5, 10−1]
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛະͷࡶԻࢄͷਪఆ 24/34 γϛϡϨʔγϣϯ݁Ռ ✓ σv2ʹରͯ͠ɼఏҊ ख๏ྑ͍ਪఆਫ਼Λୡ ͲͷࡶԻ ࢄ ఏҊख๏ʢ"TZNQUPUJD 3FTJE VBM .BUD IJOHʣ NMSE /. 4& 104 10 3 10 2 ARM ridge regularization-based scaled residual (∏ = 0.1) σ ̂2v scaled residual (∏ = 0.01) ML (oracle) 101 x Λطͱͯ͠ σ ̂2v 100 10°1 10°2 10°5 1 ̂ 22 = ∥y − A x∥ ̂ 0 M − ∥x∥ 10°4 10°3 æv2 ਅͷࡶԻ ࢄ σv2 10°2 10°1 1 = ∥y − Ax∥22 M
࣍ ✦ ઢ ٯܗ ʹର͢Δತ࠷దԽ ✦ $ (.5Λ༻͍ͨཧղੳ ✦ $ (.5Λ༻͍ͨཧղੳͷԠ༻ ✦ ❖ ະͷࡶԻࢄͷਪఆ ❖ ࠷దԽΞϧΰϦζϜͷղੳ ࠓ ޙͷలɾ·ͱΊ R . H a y a k awa, “A s ymp to ti c anal ysi s of A DMM for co m p res sed se n si ng ,” arXi v: 2009.08545, Sep. 2020.
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ ࠷ ద ԽΞϧΰϦζϜͷఆղͷղੳ ✓ 25/34 ͜Ε·Ͱͷ$ (. 5Λ༻͍ͨղੳͰɼ࠷దղ͕ओͳର ˠ ࠷ ద ԽΞϧΰϦζϜதͷ ఆతͳղͷಛ ੑʁ ࠷ద ԽΞϧΰϦζϜͷ;Δ·͍ ॳظ త ؔͷߴ ઢ ఆղ ఆ ղΛղ ੳ͢Δ͜ͱͰɼ ࠷ ద ԽΞϧΰϦζϜͷ ;Δ·͍Λௐ͍ͨ ࠷ దղ ʢ͜Ε·Ͱͷղੳͷର ʣ
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ 26/34 " %. .ʢ "M UF S O BU J O H % J SF DU JPO .F UI PE PG .V M UJ Q M J F S T ʣ ✓ "%. .͕ର ͱ͢Δ࠷ద Խ ʢ ϕ1( ⋅ ), ϕ2( ⋅ ), ΦʹͦΕͧΕ݅͋Γʣ min {ϕ1(s) + ϕ2(z) } subject to Φs = z s, z ղ͖͍ͨ ࠷ద Խ มܗ " %. .Ͱ ղ͚Δܗ 1 minN ∥y − As∥22 + λ f(s) s∈ℝ { 2 } s Λ z ʹॻ͖͑ 1 minN ∥y − As∥22 + λ f(z) subject to s = z s, z∈ℝ { 2 }
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ 27/34 " %. .ͷߋ ৽ ࣜ ✓ sͱ z Λަ৽ߋʹޓ s (k+1) ρ 1 2 = arg min ∥y − As∥2 + ∥s − z (k) + w (k)∥22 2 {2 } s∈ℝN = (A A + ρI) −1 𝖳 z (k+1) 1 minN ∥y − As∥22 + λ f(z) s . t . s = z s, z∈ℝ { 2 } 𝖳 (k) (k) A y + ρ z − w ( ( )) ρ (k) = arg min λ f(z) + ∥s − z + w (k)∥22 2 { } z∈ℝN f(s) = ∥s∥1 ͷۙࣸ૾ prox ρλ f (u) = prox ρλ f (s (k+1) + w (k)) w (k+1) =w (k) +s (k+1) −z (k+1) λ − ρ λ ρ u
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ 27/34 " %. .ͷߋ ৽ ࣜ ✓ sͱ z Λަ৽ߋʹޓ s (k+1) 1 minN ∥y − As∥22 + λ f(z) s . t . s = z s, z∈ℝ { 2 } ρ 1 2 = arg min ∥y − As∥2 + ∥s − z (k) + w (k)∥22 2 {2 } s∈ℝN = (A A + ρI) −1 𝖳 𝖳 (k) (k) A y + ρ z − w ( ( )) 1 2 ρ ͷۙࣸ૾ min f(s)= ∥s∥1ͱࣅͨܗ ∥y − As∥ લ Ͱղੳͨ͠࠷ద Խ (k+1) (k) (k) 2 2 + λf(s) N z = arg min λ f(z) + s∈ℝ ∥s {−2z + w ∥2 } 2 { } prox ρλ f (u) z∈ℝN = prox ρλ f (s (k+1) + w (k)) w (k+1) =w (k) +s (k+1) −z (k+1) λ − ρ λ ρ u
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ ෦ ͷղੳ ✓ 28/34 "%. .ͷߋ ৽ ࣜʹ·ؚΕΔ෦ Λ$( .5Ͱղੳ ෦ s (k+1) ρ 1 2 = arg min ∥y − As∥2 + ∥s − z (k) + w (k)∥22 2 {2 } s∈ℝN $( . 5Ͱղ ੳʢ ৄࡉল ུʣ k = 0, 1, 2, …ʹରͯ͠ɼM, N → ∞Ͱ 1 (k+1) 2 2 P 2 ∥s − x∥2 α* − σ ֬ ऩ ଋ ʣ ✦ ɹ ( k) vʢ N ✦ s (k+1)ͷ ͷ ͕ɼεΧϥʔͷ֬ ม ̂ (α*, β*) = Sk+1 k k β* Δ k 1 β* Δ k α* k +ρ α* k ͷ ʹʢ͋Δҙ ຯͰʣऩ ଋ ( X+ α* k Δ ) H + ρ(Zk − Wk) , β* (α* k k )ɿ͋Δ࠷దԽ ͷղ
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ " %. .ͷղ ੳ ݁Ռͷ·ͱΊ ✓ 29/34 "%. .ͷߋ ৽ ࣜʹରԠ͢ΔεΧϥʔͷ֬ ա ఔΛಘΒΕΔ s (k+1) ρ 1 2 = arg min ∥y − As∥2 + ∥s − z (k) + w (k)∥22 2 {2 } s∈ℝN "%. .ͷ ߋ৽ࣜ z (k+1) = prox λ f (s (k+1) + w (k)) ρ w (k+1) = w (k) + s (k+1) − z (k+1) ର Ԡ͢Δ ֬ աఔ ̂ (α*, β*) Sk+1 = Sk+1 k k Zk+1 = prox ρλ f (Sk+1 + Wk) Wk+1 = Wk + Sk+1 − Zk+1 ֬ ม Sk, Zk, Wk ͷ࣮ ݱΛଟͭ͘Δ͜ͱͰɼ "%..ͷ֤ ෮Ͱͷਪ ఆ s (k) ͷۙ తͳࠩ ޡΛ༧ ଌ Մ ೳ
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ 30/34 γϛϡϨʔγϣϯ݅ ✓ ػࢉ ܭγϛϡϨʔγϣϯͰ ✦ " %. .ͷ֤ ෮Ͱͷਪఆ s (k) ͷ.4&ͷมԽ ✦ ཧ ղ ੳ ݁ Ռ͔ΒಘΒΕΔۙ త.4 &ͷมԽ ɹΛൺֱ ؍ଌ Δ = M/N = 0.7 M y = ֬ 0.9 Ͱ 0 ɼ֬ 0.1 Ͱඪ ४Ψε ʹै͏ N A x + v ࡶ Ի ࢄ σv2 = 0.0001 " % ..ͷύϥϝʔλ ρ = 0.1 ֤ ෮Ͱͷਪ ఆs (k) (k = 0,1,2,…)
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ 31/34 γϛϡϨʔγϣϯ݁Ռ ✓ N ͕े େ͖͍ ߹ɼ ֤ ෮Ͱ࣮ࡍͷ. 4&ͱ ۙత .4&͕͍ۙͱͳΔ 100 empirical (N = 50) empirical (N = 100) empirical (N = 500) . 4& MSE 10°1 empirical (N = 1000) prediction asymptotic MSE of optimizer 10°2 ࣮ ࡍͷ.4 & 10°3 ࠷ ద ղͷۙ త . 4&ʹऩ ଋ ۙ త .4& 10°4 0 ࠷ ద ղͷ ۙత .4& 5 10 15 20 number of iterations " %. .ͷ෮ճ 25 30
$(.5Λ༻͍ͨཧղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ 32/34 ଞͷ࠷ద ԽΞϧΰϦζϜͷղੳ ✓ %PV H MB T 3B D IG P SEΞϧΰϦζϜͷղੳՄೳ s % PV H MB T 3 B D IG P S E ΞϧΰϦζϜ (k+1) 1 1 2 ∥y − As∥2 + ∥s − z (k)∥22 = arg min 2γ {2 } s∈ℝN 1 = A A+ I ( γ ) −1 𝖳 1 (k) A y+ z ( ) γ 𝖳 ύϥϝʔλ z (k+1) = z (k) + ρk (proxγλf (2s (k+1) − z (k)) − s (k+1)) Sk+1 = ର Ԡ͢Δ ֬ աఔ β̃*k Δ 1 β̃*k Δ α̃*k + 1 γ α̃*k ( X+ α̃*k 1 H + Zk Δ ) γ Zk+1 = Zk + ρk (proxγλf (2Sk+1 − Zk) − Sk+1) (α̃*k , β̃*k )ɿ͋Δ࠷దԽ ͷղ
࣍ ✦ ઢ ٯܗ ʹର͢Δತ࠷దԽ ✦ $ (.5Λ༻͍ͨཧղੳ ✦ $ (.5Λ༻͍ͨཧղੳͷԠ༻ ✦ ❖ ະͷࡶԻࢄͷਪఆ ❖ ࠷దԽΞϧΰϦζϜͷղੳ ࠓ ޙͷలɾ·ͱΊ
ࠓޙͷలɾ·ͱΊ 33/34 ࠓ ޙͷల $ ( . 5ͷద༻ൣ ғͷ֦ େ Aɿʁʁʁ Aɿ J J E Ψε ޯ Λ༻͍ΔΞϧΰϦζϜͷղੳ ∂ 1 ∥y − As∥22 = A 𝖳( y − As)ͷ ∂s 2 ۙ త;Δ·͍ʁ ΑΓγϯϓϧͳิ ॿ ʢ "0 (α*, β*)Λด Ͱࣜ ܗಘΒΕͳ͍͔ʁ ղੳ ݁Ռʹͮ͘جύϥϝʔλઃ ܭɾΞϧΰϦζϜσβΠϯ ✦ ۙత . 4&Λ࠷খʹ͢ΔύϥϝʔλͷΛద Ԡతʹਪఆ ✦ ղੳ݁ ՌΛͯ͠ʹجɼΑΓޮ ੑ ೳ͕ྑ͍ΞϧΰϦζϜΛσβΠϯ
ࠓޙͷలɾ·ͱΊ 34/34 ·ͱΊ ✓ $(. 5ʹͮ͘جತ࠷ దԽ ͷཧ ղੳͱͦͷԠ༻ʹ͍ͭͯհ N M y = A x + v ओʢ10 1 ∥y − As∥22 + λ f(s) ਪ ఆ x̂ = arg min {2 } s∈ℝN e∈𝒮e u∈𝒮u ิॿ ʢ"0 min max {∥e∥2 g 𝖳u − ∥u∥2 h 𝖳e + ξ(e, u)} $ (. 5 1 2 ✦ ۙత . 4&ɿ ∥x̂ − x∥2 N 1 ✦ ۙత ࠩɿ ∥y − A x∥ ̂ 22 N min max {u 𝖳Ge + ξ(e, u)} e∈𝒮e u∈𝒮u P (α*)2 − σv2 P (β*) 2 ✦ ࡶԻ ࢄͷਪఆ ✦ ࠷దԽΞϧΰϦζϜͷղੳ ʹԠ༻Մೳ