【招待講演】線形逆問題に対する凸最適化問題の特性解析とその応用

3.6K Views

August 24, 21

スライド概要

電子情報通信学会 信号処理研究会(2021/08/24)

開催プログラム:https://www.ieice.org/ken/program/index.php?tgs_regid=cb0654c999afe7fe2e1a821190ed08bd383d6b9b1ded7f62427b2789f35687e7&tgid=IEICE-SIP

profile-image

東京農工大学大学院工学研究院 准教授

シェア

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

20 2 1/ 08/24 ৴ ߸ॲཧ ‫ ڀ ݚ‬ձ ઢ ‫ ٯ ܗ‬໰ ୊ʹର͢Δತ࠷దԽ໰୊ͷ ಛ ੑ ղ ੳͱͦͷԠ༻ େ ࡕେֶ େ ֶ Ӄ‫ ڀ ݚ ֶ ޻ૅ ج‬Պ ૣ઒ྒ

2.

໨࣍ ✦ ઢ ‫ ٯܗ‬໰ ୊ʹର͢Δತ࠷దԽ  ✦ $ (.5Λ༻͍ͨཧ࿦ղੳ ✦ $ (.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ ✦ ❖ ະ஌ͷࡶԻ෼ࢄͷਪఆ ❖ ࠷దԽΞϧΰϦζϜͷղੳ ࠓ ‫ޙ‬ͷల๬ɾ·ͱΊ

3.

໨࣍ ✦ ઢ ‫ ٯܗ‬໰ ୊ʹର͢Δತ࠷దԽ ✦ $ (.5Λ༻͍ͨཧ࿦ղੳ ✦ $ (.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ ✦ ❖ ະ஌ͷࡶԻ෼ࢄͷਪఆ ❖ ࠷దԽΞϧΰϦζϜͷղੳ ࠓ ‫ޙ‬ͷల๬ɾ·ͱΊ

4.

ઢ‫ٯܗ‬໰୊ʹର͢Δತ࠷దԽ 1/34 ઢ‫ٯܗ‬໰୊ ✓ ະ ஌ϕΫτϧ x ∈ ℝN Λ ͦͷઢ ‫ ؍ ܗ‬ଌ  y = Ax + v ∈ ℝM ͔Βਪఆ N M y = A x + v ࡶԻ ਪ ఆ஋  x̂ ྫɿ ✦ ૹ৴ ৴߸ ਪఆʢແ ઢ௨৴ ʣ ✦ ը૾ ෮‫ݩ‬ ʢը ૾ॲ ཧʣ ✦ ઢ‫ܗ‬ճ‫ؼ‬ʢ‫ػ‬ց ֶशʣ

5.

ઢ‫ٯܗ‬໰୊ʹର͢Δತ࠷దԽ 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.

6.
[beta]
ઢ‫ٯܗ‬໰୊ʹର͢Δತ࠷దԽ

ѹ ॖηϯγϯάͷΞϧΰϦζϜ
✓

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.

7.

ઢ‫ٯܗ‬໰୊ʹର͢Δತ࠷దԽ 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

8.

ઢ‫ٯܗ‬໰୊ʹର͢Δತ࠷దԽ 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

9.

໨࣍ ✦ ઢ ‫ ٯܗ‬໰ ୊ʹର͢Δತ࠷దԽ  ✦ $ (.5Λ༻͍ͨཧ࿦ղੳ ✦ $ (.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ ✦ ❖ ະ஌ͷࡶԻ෼ࢄͷਪఆ ❖ ࠷దԽΞϧΰϦζϜͷղੳ ࠓ ‫ޙ‬ͷల๬ɾ·ͱΊ

10.
[beta]
$(.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.

11.

$(.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

12.

$(.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  ʢ࠷ దղ͕ू߹ 𝒮 ʹଐ͢Δʣ

13.
[beta]
$(.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 

ʢ࠷ దղ͕ू߹ 𝒮 ʹଐ͢Δʣ

14.
[beta]
$(.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 

ʢ࠷ దղ͕ू߹ 𝒮 ʹଐ͢Δʣ

15.

$(.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 ʣͷ ղੳ ݁Ռ

16.

$(.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 ʣͷ ղੳ ݁Ռ

17.

$(.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 ഒ

18.

$(.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

19.

$(.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 ʣͷ ղੳ ݁Ռ

20.

$(.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  ʹؔ͢Δٞ࿦΋ඞ ཁ

21.

$(.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 ʣͷ ղੳ ݁Ռ

22.

$(.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

23.

$(.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)

24.

$(.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ʢ  ֬཰ऩଋʣ

25.

$(.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ʢ  ֬཰ऩଋʣ

26.

$(.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

27.

$(.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

28.

$(.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.

29.

໨࣍ ✦ ઢ ‫ ٯܗ‬໰ ୊ʹର͢Δತ࠷దԽ  ✦ $ (.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.

30.

$(.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

31.
[beta]
$(.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.

32.

$(.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Λ࢖ͬͯ‫ࢉ ܭ‬ ͷղ

33.

$(.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

34.

$(.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 ͷਪఆΛ‫܁‬Γฦ͢͜ͱͰਪ ఆ ਫ਼ ౓Λվ ળ Մ ೳ

35.

$(.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]

36.

$(.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

37.

໨࣍ ✦ ઢ ‫ ٯܗ‬໰ ୊ʹର͢Δತ࠷దԽ  ✦ $ (.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.

38.

$(.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ ࠷ ద ԽΞϧΰϦζϜͷ࢑ఆղͷղੳ ✓ 25/34 ͜Ε·Ͱͷ$ (. 5Λ༻͍ͨղੳͰ͸ɼ࠷దղ͕ओͳର৅  ˠ ࠷ ద ԽΞϧΰϦζϜதͷ࢑ ఆతͳղͷಛ ੑ͸ʁ ࠷ద ԽΞϧΰϦζϜͷ;Δ·͍ ॳ‫ظ‬஋ ໨త ؔ਺ͷ౳ߴ ઢ ࢑ ఆղ ࢑ ఆ ղΛղ ੳ͢Δ͜ͱͰɼ ࠷ ద ԽΞϧΰϦζϜͷ ;Δ·͍Λௐ΂͍ͨ ࠷ దղ  ʢ͜Ε·Ͱͷղੳͷର ৅ʣ

39.

$(.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 }

40.

$(.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

41.

$(.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

42.

$(.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 )ɿ͋Δ࠷దԽ ໰୊ͷղ

43.

$(.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)  ͷ઴ۙ తͳ‫ࠩ ޡ‬Λ༧ ଌ Մ ೳ

44.

$(.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,…)

45.

$(.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

46.

$(.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 )ɿ͋Δ࠷దԽ ໰୊ͷղ

47.

໨࣍ ✦ ઢ ‫ ٯܗ‬໰ ୊ʹର͢Δತ࠷దԽ  ✦ $ (.5Λ༻͍ͨཧ࿦ղੳ ✦ $ (.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ ✦ ❖ ະ஌ͷࡶԻ෼ࢄͷਪఆ ❖ ࠷దԽΞϧΰϦζϜͷղੳ ࠓ ‫ޙ‬ͷల๬ɾ·ͱΊ

48.

ࠓ‫ޙ‬ͷల๬ɾ·ͱΊ 33/34 ࠓ ‫ޙ‬ͷల ๬ $ ( . 5ͷద༻ൣ ғͷ֦ େ  Aɿʁʁʁ  Aɿ J  J  E  Ψ΢ε෼෍ ޯ ഑Λ༻͍ΔΞϧΰϦζϜͷղੳ ∂ 1 ∥y − As∥22 = A 𝖳( y − As)ͷ ∂s 2 ઴ۙ త;Δ·͍͸ʁ ΑΓγϯϓϧͳิ ॿ ໰୊ʢ "0 (α*, β*)Λด ‫Ͱࣜ ܗ‬ಘΒΕͳ͍͔ʁ ղੳ ݁Ռʹ‫ͮ͘ج‬ύϥϝʔλઃ ‫ܭ‬ɾΞϧΰϦζϜσβΠϯ ✦ ઴ۙత . 4&Λ࠷খʹ͢Δύϥϝʔλͷ஋Λద Ԡతʹਪఆ  ✦ ղੳ݁ ՌΛ‫ͯ͠ʹج‬ɼΑΓޮ ཰΍ੑ ೳ͕ྑ͍ΞϧΰϦζϜΛσβΠϯ

49.

ࠓ‫ޙ‬ͷల๬ɾ·ͱΊ 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 ✦ ࡶԻ෼ ࢄͷਪఆ ✦ ࠷దԽΞϧΰϦζϜͷղੳ ʹ΋Ԡ༻Մೳ