---
title: 【招待講演】線形逆問題に対する凸最適化問題の特性解析とその応用
tags:  #圧縮センシング  
author: [Ryo Hayakawa](https://convert.docswell.com/user/rhayakawa)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/5DEYR21QJM.jpg?width=480
description: 電子情報通信学会 信号処理研究会（2021/08/24）   開催プログラム：https://www.ieice.org/ken/program/index.php?tgs_regid=cb0654c999afe7fe2e1a821190ed08bd383d6b9b1ded7f62427b2789f35687e7&amp;tgid=IEICE-SIP
published: August 24, 21
canonical: https://convert.docswell.com/s/rhayakawa/5R892Z-SIP202108
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/5DEYR21QJM.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/2VJND82278.jpg)

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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/GYE9GK1DJ3.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/5GE8VR45ED.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/MLEL5K637R.jpg)

ઢ‫ٯܗ‬໰୊ʹର͢Δತ࠷దԽ
2/34
ѹ ॖηϯγϯά &lt; &gt;
✓
εύʔεͳʢ ྵ ੒ ෼͕ଟ͍ʣະ஌ϕΫτϧ x ∈ ℝN Λ
ͦͷઢ ‫ ؍ ܗ‬ଌ  y = Ax + v ∈ ℝM ͔Βਪఆ
N
M
y =
A
ඇྵ ੒෼
x + v
ࡶԻ
ਪ ఆ஋  x̂
ྫɿ ✦ .3 *ը ૾࠶ ߏ੒ &lt;  &gt;
ʢ.BHOFUJ D3 FTPOBOD F*N BHJOHʣ
✦
ແઢ ௨৴ ࿏ਪ ఆ &lt; &gt;
[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.


# Page. 6

![Page Image](https://bcdn.docswell.com/page/54JM325MEW.jpg)

ઢ‫ٯܗ‬໰୊ʹର͢Δತ࠷దԽ
ѹ ॖηϯγϯάͷΞϧΰϦζϜ
✓
3/34
ѹ ॖηϯγϯάʹର͢Δ༷ʑͳख ๏͕ఏҊ͞Ε͍ͯΔ
✦
ᩦཉ๏ɿඇྵ੒ ෼ͷ৔ॴΛॱ ൪ʹਪ ఆ
❖
❖
✦
0 .1ʢ0SU IPHPOBM. 1ʣ&lt;  &gt; ͳͲ
ϝοηʔδ఻೻๏ɿ֬཰ʢ ৴ ೦ ʣ఻ ೻๏ͷۙࣅ 
❖
✦
. 1ʢ.BUDI JOH1VSTVJUʣ&lt;  &gt; 
&quot;. 1ʢ&quot;QQSPYJNBU F.FTTBHF1BTTJOHʣ&lt;  &gt; ͳͲ
࠷దԽɿ໨తؔ ਺ͷ࠷খ Խ 
❖
❖
* 45 &quot;ʢ* UF SBUJWF4PGU 5ISFTIPME JOH&quot;M HPSJUIN ʣ&lt;  &gt; 
&#039; *45&quot;ʢ&#039;BTU*45&quot;ʣ&lt;  &gt; ͳͲ
[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.


# Page. 7

![Page Image](https://bcdn.docswell.com/page/ZPJRQM3L79.jpg)

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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/NPEX5V967X.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/63EK6QPGED.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/4L736PX575.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
ਪ ఆ ஋ͷ‫ࠩ ޡ‬ͷղ ੳ
✓
1
ਪ ఆ஋ 
     ∥y
  − As∥
   22 +
 λ f(s)
     ͷ‫ࠩޡ‬Λ஌Γ͍ͨ
x̂ = argmin
{2
}
s∈ℝN
ղੳͷΞϓϩʔν
✦
1
ྫɿ.4 &amp;ʢ. F BO 4RVB SF E&amp;SSPSʣ ∥x̂ − x∥22
N
ϝοηʔδ఻ ೻ ๏ʹ‫ͮ͘ج‬ղ ੳ  &lt;   &gt;
❖
✦
6/34
ϝοηʔδ఻ ೻ ๏ͷಛ ੑΛղ ੳ ˠ  ࠷ దԽ໰୊ͱͷؔ܎Λٞ࿦
$( . 5ʢ$POWFY(B VTTJBO.JONB Y 5IFP SFNʣʹ‫ͮ͘ج‬ղ ੳ  &lt;      &gt; 
❖
࠷ ద Խ໰ ୊Λগ͠ม ‫ͨ͠ܗ‬΋ͷΛղ ੳ
[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.


# Page. 11

![Page Image](https://bcdn.docswell.com/page/V87DVL2Y7G.jpg)

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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/4VJPV212J8.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
8/34
$( . 5ʢͷΠϝʔδʣ
✓
ओ ໰୊ʢ 1 SJ N BS Z  0 Q U JN J[B UJ PO  10ʣͱ
ิ ॿ໰ ୊ʢ &quot; V YJM J B S Z  0 Q U JN J[B UJ PO  &quot;0ʣΛؔ࿈෇͚Δఆཧ
ʢ10ʣ
ʢ&quot; 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 → ∞Ͱ ϕ̄ &lt; ϕ̄𝒮c 
ʢ࠷ దղ͕ू߹ 𝒮 ʹଐ͢Δʣ


# Page. 13

![Page Image](https://bcdn.docswell.com/page/L2EVZDYX7Q.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
8/34
$( . 5ʢͷΠϝʔδʣ
ξ : ℝN × ℝM → ℝɿ
eʹؔͯ͠͸ತؔ਺ ɼ
✓ ओ ໰୊
ʢ 1 SJMN BS Z  0 Q U JN J[B UJ PO  10ʣͱ uʹؔͯ͠͸Ԝؔ ਺
N
𝒮e ⊂ ℝ , 𝒮u ⊂ ℝ ɿίϯύΫτू߹
ิ ॿ໰ ୊ʢ &quot; V YJM J B S Z  0 Q U JN J[B UJ PO  &quot;0ʣΛؔ࿈෇͚Δఆཧ
G ∈ ℝM×N, g ∈ ℝM, h ∈ ℝNɿ֤੒෼͕ಠཱʹඪ४Ψ΢ε෼෍
ʢ10ʣ
ʢ&quot; 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 → ∞Ͱ ϕ̄ &lt; ϕ̄𝒮c 
ʢ࠷ దղ͕ू߹ 𝒮 ʹଐ͢Δʣ


# Page. 14

![Page Image](https://bcdn.docswell.com/page/Z57G4Y9REL.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
8/34
$( . 5ʢͷΠϝʔδʣ
ξ : ℝN × ℝM → ℝɿ
eʹؔͯ͠͸ತؔ਺ ɼ
✓ ओ ໰୊
ʢ 1 SJMN BS Z  0 Q U JN J[B UJ PO  10ʣͱ uʹؔͯ͠͸Ԝؔ ਺
N
𝒮e ⊂ ℝ , 𝒮u ⊂ ℝ ɿίϯύΫτू߹
ิ ॿ໰ ୊ʢ &quot; V YJM J B S Z  0 Q U JN J[B UJ PO  &quot;0ʣΛؔ࿈෇͚Δఆཧ
G ∈ ℝM×N, g ∈ ℝM, h ∈ ℝNɿ֤੒෼͕ಠཱʹඪ४Ψ΢ε෼෍
ʢ10ʣ
ʢ&quot; 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
𝒮
௚ ‫ײ‬తʹ͸ʜ
𝒮
ิ ॿ ໰୊ʢ&quot; 0 ʣͷղ͕ߴ ֬ ཰Ͱू߹ 𝒮 ʹଐ͢Δ
ˠ ओ໰ ୊ʢ 10 ʣͷղ΋ߴ ֬ ཰Ͱू߹ 𝒮 ʹଐ͢Δ
ϕ̄𝒮c
ϕ̄
ओ ໰୊ʢ 10 ʣͷ୅ΘΓʹิ ॿ໰ ୊ʢ &quot;0 ʣΛղੳͯ͠΋Α͍
e
̂
̂
eΦ
e
̂ ∈ 𝒮) = 1
lim Pr (eΦ
M, N→∞
eϕ
৚݅ɿ M, N → ∞Ͱ ϕ̄ &lt; ϕ̄𝒮c 
ʢ࠷ దղ͕ू߹ 𝒮 ʹଐ͢Δʣ


# Page. 15

![Page Image](https://bcdn.docswell.com/page/V4EQGMWYJP.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
9/34
$( . 5Λ༻͍ͨղੳʛ֓ཁ
✓
1
2
̂
∥
x
−
x∥
$(. 5Λ༻͍ͯਪ ఆ஋ͷ. 4 &amp;         2Λղੳ͢Δखॱ
N
1
‫ݩ‬ͷ࠷ద Խ ໰୊ min
2
λ
f(s)
∥y
−
As∥


+
2
ʢղ ੳͷର ৅ ʣ s∈ℝN { 2
}
ओ ໰୊ʢ 1 0 ʣͷ‫ʹܗ‬ม‫ܗ‬
ओ໰ ୊ʢ 10 ʣͷ
ղੳ ݁Ռ
ओ໰ ୊ʢ 1 0 ʣ
ิ ॿ໰ ୊ʢ &quot;0 ʣΛಋग़
ิॿ ໰୊ʢ &quot; 0 ʣ
‫ݩ‬ͷ࠷ దԽ ໰ ୊ͷ
ղੳ݁Ռ
ิ ॿ ໰୊ʢ&quot; 0 ʣΛղ ੳ
$ (. 5
ิॿ ໰୊ʢ&quot;0 ʣͷ
ղੳ ݁Ռ


# Page. 16

![Page Image](https://bcdn.docswell.com/page/DKJ45VKZE1.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
9/34
$( . 5Λ༻͍ͨղੳʛ֓ཁ
✓
1
2
̂
∥
x
−
x∥
$(. 5Λ༻͍ͯਪ ఆ஋ͷ. 4 &amp;         2Λղੳ͢Δखॱ
N
1
‫ݩ‬ͷ࠷ద Խ ໰୊ min
2
λ
f(s)
∥y
−
As∥


+
2
ʢղ ੳͷର ৅ ʣ s∈ℝN { 2
}
ओ ໰୊ʢ 1 0 ʣͷ‫ʹܗ‬ม‫ܗ‬
ओ໰ ୊ʢ 10 ʣͷ
ղੳ ݁Ռ
ओ໰ ୊ʢ 1 0 ʣ
ิ ॿ໰ ୊ʢ &quot;0 ʣΛಋग़
ิॿ ໰୊ʢ &quot; 0 ʣ
‫ݩ‬ͷ࠷ దԽ ໰ ୊ͷ
ղੳ݁Ռ
ิ ॿ ໰୊ʢ&quot; 0 ʣΛղ ੳ
$ (. 5
ิॿ ໰୊ʢ&quot;0 ʣͷ
ղੳ ݁Ռ


# Page. 17

![Page Image](https://bcdn.docswell.com/page/PLE1W3XDJG.jpg)

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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/8GEW6PN8E2.jpg)

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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/W47ZYK39E3.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
$( . 5Λ༻͍ͨղੳʛ֓ཁ
✓
1
2
̂
∥
x
−
x∥
$(. 5Λ༻͍ͯਪ ఆ஋ͷ. 4 &amp;         2Λղੳ͢Δखॱ
N
1
‫ݩ‬ͷ࠷ద Խ ໰୊ min
2
λ
f(s)
∥y
−
As∥


+
2
ʢղ ੳͷର ৅ ʣ s∈ℝN { 2
}
ओ ໰୊ʢ 1 0 ʣͷ‫ʹܗ‬ม‫ܗ‬
ओ໰ ୊ʢ 10 ʣͷ
ղੳ ݁Ռ
ओ໰ ୊ʢ 1 0 ʣ
ิ ॿ໰ ୊ʢ &quot;0 ʣΛಋग़
ิॿ ໰୊ʢ &quot; 0 ʣ
‫ݩ‬ͷ࠷ దԽ ໰ ୊ͷ
ղੳ݁Ռ
ิ ॿ ໰୊ʢ&quot; 0 ʣΛղ ੳ
$ (. 5
ิॿ ໰୊ʢ&quot;0 ʣͷ
ղੳ ݁Ռ


# Page. 20

![Page Image](https://bcdn.docswell.com/page/KYJ6DQXD7V.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
$( . 5Λ༻͍ͨղੳʛʢ &quot;0ʣͷಋग़
✓
12/34
ओ ໰୊ʢ 1 0 ʣʹର Ԡ͢Δิ ॿ໰ ୊ʢ &quot;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
ʢ &quot;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  ʹؔ͢Δٞ࿦΋ඞ ཁ


# Page. 21

![Page Image](https://bcdn.docswell.com/page/5GJ53RX8E4.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
$( . 5Λ༻͍ͨղੳʛ֓ཁ
✓
1
2
̂
∥
x
−
x∥
$(. 5Λ༻͍ͯਪ ఆ஋ͷ. 4 &amp;         2Λղੳ͢Δखॱ
N
1
‫ݩ‬ͷ࠷ద Խ ໰୊ min
2
λ
f(s)
∥y
−
As∥


+
2
ʢղ ੳͷର ৅ ʣ s∈ℝN { 2
}
ओ ໰୊ʢ 1 0 ʣͷ‫ʹܗ‬ม‫ܗ‬
ओ໰ ୊ʢ 10 ʣͷ
ղੳ ݁Ռ
ओ໰ ୊ʢ 1 0 ʣ
ิ ॿ໰ ୊ʢ &quot;0 ʣΛಋग़
ิॿ ໰୊ʢ &quot; 0 ʣ
‫ݩ‬ͷ࠷ దԽ ໰ ୊ͷ
ղੳ݁Ռ
ิ ॿ ໰୊ʢ&quot; 0 ʣΛղ ੳ
$ (. 5
ิॿ ໰୊ʢ&quot;0 ʣͷ
ղੳ ݁Ռ


# Page. 22

![Page Image](https://bcdn.docswell.com/page/4LE36PXGE5.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
$( . 5Λ༻͍ͨղੳʛʢ &quot;0ʣͷม‫ܗ‬
✓
13/34
ิ ॿ໰ ୊ʢ &quot; 0 Λม ‫ܗ‬
ʢ &quot;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 
α&gt;0
β≥0
{
αβ Δ
2
+
σv2 β Δ
2α
β2
αβ
−
−

2
2 Δ
                   +
pX ʹै͏֬཰ม਺
ඪ४Ψ΢εม਺
E env αλ f X +
β Δ (
α
[
β Δ
H
Δ )]}
α
.P SF BVF OW F MP QF


# Page. 23

![Page Image](https://bcdn.docswell.com/page/V8EDVL2NEG.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
$( . 5Λ༻͍ͨղੳʛʢ &quot;0ʣͷղੳ
✓
14/34
ิ ॿ໰ ୊ʢ &quot; 0 ͷղΛղ ੳ
min max 
α&gt;0
β≥0
{
αβ Δ
2
+
σv2 β Δ
2α
β2
αβ

−
−
2
2 Δ
                   +
pX ʹै͏֬཰ม਺
ඪ४Ψ΢εม਺
E env αλ f X +
β Δ (
α
[
β Δ
H
Δ )]}
α
.P SF BVF OW F MP QF
✦ ˢͷղΛ (α*, β*) 
̂
✦ ิॿ໰୊ʢ&quot;0ʣͷղΛe(AO)
ͱ͓͘
 M, N → ∞ Ͱ
1
P
2
̂ ∥2
(α*)2 − σv2ʢ
 ∥e(AO)
 ֬཰ ऩ ଋʣ
N
̂
= x̂ − x ʹ্ͷ݁ՌΛద༻
$(.5Λ༻͍ͯɼओ໰୊ʢ10 ͷղ e(PO)


# Page. 24

![Page Image](https://bcdn.docswell.com/page/4V7PV21N78.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
$( . 5Λ༻͍ͨղੳʛ݁Ռ
15/34
f(s) =∥s∥
ℓ1 ਖ਼ଇ Խ 
 Λ༻͍ͨ࠷
దԽ ໰୊ͷղੳ݁Ռ
1
✓
Ծ ఆɿ
✦
✦
‫ ؍‬ଌ ߦྻ  A ∈ ℝM×N ͷ֤ ੒ ෼͸ಠ ཱʹฏ ‫ ۉ‬0ɾ෼ࢄ 1/N ͷΨ΢ε෼ ෍ 
ࡶ ԻϕΫτϧ v ∈ ℝM ͷ֤ ੒ ෼͸ಠཱʹฏ‫ ۉ‬0ɾ෼ࢄ σv2 ͷΨ΢ε෼ ෍
࠷ దԽ໰ ୊
min max 
α&gt;0
β≥0
{
αβ Δ
2
+
σv2 β Δ
2α
β Δ
β2
αβ
α
+
E env αλ f X +
H
−
−
β Δ (
α
2
2 Δ
Δ ) }
͕ͨͩ̍ͭͷղ (α*, β*) Λ΋ͭ
1
M, N → ∞Ͱ ∥x̂ − x∥22
N
P
(α*)2 − σv2ʢ
 ֬཰ऩଋʣ


# Page. 25

![Page Image](https://bcdn.docswell.com/page/L2JVZDYYEQ.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
$( . 5Λ༻͍ͨղੳʛ݁Ռ
15/34
f(s) =∥s∥
ℓ1 ਖ਼ଇ Խ 
 Λ༻͍ͨ࠷
దԽ ໰୊ͷղੳ݁Ռ
1
✓
Ծ ఆɿ
‫ ؍‬ଌ ߦྻ  A ∈ ℝM×N ͷ֤ ੒ ෼͸ಠ ཱʹฏ ‫ ۉ‬0ɾ෼ࢄ 1/N ͷΨ΢ε෼ ෍ 
(α, β)

2
M  ͷ࠷ద Խ໰ ୊Λղ͘ͱɼ
✦ ࡶ ԻϕΫτϧ v ∈ ℝ ͷ֤ ੒ ෼͸ಠཱʹฏ‫ ۉ‬0ɾ෼ࢄ σv ͷΨ΢ε෼ ෍
ਪ ఆ ஋ x̂ ͷ઴ۙత .4&amp;͕‫·ٻ‬Δ
࠷ దԽ໰ ୊
✦
min max 
α&gt;0
β≥0
{
αβ Δ
2
+
σv2 β Δ
2α
β Δ
β2
αβ
α
+
E env αλ f X +
H
−
−
β Δ (
α
2
2 Δ
Δ ) }
͕ͨͩ̍ͭͷղ (α*, β*) Λ΋ͭ
1
M, N → ∞Ͱ ∥x̂ − x∥22
N
P
(α*)2 − σv2ʢ
 ֬཰ऩଋʣ


# Page. 26

![Page Image](https://bcdn.docswell.com/page/Z5EG4Y9WJL.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
16/34
γϛϡϨʔγϣϯ৚݅
✓
‫ػࢉ ܭ‬γϛϡϨʔγϣϯͰ
✦
✦
1
2
̂
∥
x
−
x∥
࣮ ࡍʹਪ ఆΛߦͬͨͱ͖ͷ. 4 &amp;
2
N
2
(α*)
− σv2
ཧ ࿦ղ ੳ ݁ Ռ͔ΒಘΒΕΔ઴ۙ త.4 &amp;
ɹΛൺֱ
‫؍‬ଌ ཰ Δ = 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


# Page. 27

![Page Image](https://bcdn.docswell.com/page/V4JQGMWQ7P.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
17/34
γϛϡϨʔγϣϯ݁Ռ
N ͕े෼ େ͖͍৔ ߹ɼ࣮ࡍͷ. 4 &amp;ͱ઴ ۙత.4&amp;͕͍ۙ஋ͱͳΔ
10°1
empirical (N = 50)
empirical (N = 100)
empirical (N = 500)
10°2
࣮ ࡍͷ.4 &amp;
empirical (N = 1000)
prediction
.
4&amp;
MSE
✓
઴ ۙ త .4 &amp;
10°3
λ = 0.02 ෇ ͕ۙྑ͍ύϥϝʔλͷ஋
10°4
0.02
0.04
0.06
ਖ਼ ଇԽύϥϝʔλ λ
∏
0.08
0.10


# Page. 28

![Page Image](https://bcdn.docswell.com/page/DK745VKYJ1.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳ
$( . 5Λ༻͍ͨղੳʹؔ͢Δ‫ڀݚ‬
✦
ΑΓҰ ൠ తͳ࠷ ద Խ ໰୊ͷ. 4 &amp;ͷղੳ &lt;   &gt; 
✦
཭ ࢄ஋ΛͱΔ৴ ߸ͷਪఆʹର͢Δ
18/34
4&amp;3ʢ 4 ZNC P M  &amp;S SP S 3 BUF ʣͷղ ੳ &lt;     &gt; 
✦
ඇ ઢ‫ ؍ ܗ‬ଌ͔Βͷਪ ఆ΁ͷԠ༻ &lt;  &gt; 
✦
‫ ؍‬ଌߦ ྻͷ৘ ใʹ‫·ؚ͕ࠩ ޡ‬Ε͍ͯΔ৔߹ͷ‫ݕ‬౼ &lt;   &gt; 
✦
ෳ ૉ਺ ྖ Ҭͷઢ ‫ ٯܗ‬໰୊΁ͷԠ༻ &lt;  &gt;
[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.


# Page. 29

![Page Image](https://bcdn.docswell.com/page/PLJ1W3XN7G.jpg)

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


# Page. 30

![Page Image](https://bcdn.docswell.com/page/8GJW6PKMJ2.jpg)

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


# Page. 31

![Page Image](https://bcdn.docswell.com/page/W4EZYKZMJ3.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ʛະ஌ͷࡶԻ෼ࢄͷਪఆ
઴ ۙ త ղ ੳʹ‫ͮ͘ج‬৴߸ରࡶԻൺͷਪఆ
✓
20/34
Ϧοδਖ਼ ଇԽΛ༻͍ͨ࠷ దԽͷ઴ ۙత ղੳʹ‫ͮ͘ج‬
৴ ߸ର ࡶ Իൺͷਪ ఆ &lt;   &gt;
ਖ਼ଇ Խύϥϝʔλ τ  Λ‫ ݻ‬ఆͨ͠ͱ͖ͷ໨తؔ਺ͷ࠷ద஋
1
Θ(τ) = minN
∥y − As∥22 +  τ ∥s∥22
s∈ℝ { 2
}
Ϧοδਖ਼ଇ Խ
ʹରͯ͠ɼM, N͕े ෼ େ͖͍ͱ͖
Θ(τ) ≈ θ1(τ) σx2 + θ2(τ) σv2
τ ͷؔ਺ 
ʢ ‫ ࢉ ܭ‬Մ ೳʣ
x ͷ੒ ෼ͷ෼ࢄ
ෳ਺ͷ τ  ʹؔ͢ΔࣜΛཱͯͯ
σx2, σv2ʹ͍ͭͯղ͘
✦ x ͷੑ ࣭ʢεύʔεੑͳͲʣΛ‫͍ͳ͖Ͱ༻׆‬
✦ M &lt; 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.


# Page. 32

![Page Image](https://bcdn.docswell.com/page/KY76DQZ5EV.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ʛະ஌ͷࡶԻ෼ࢄͷਪఆ
઴ ۙ తͳ࢒ࠩ
✓
21/34
1
$(. 5Λ༻͍Δͱɼ࢒ࠩ   ∥y
 −
 A
 x∥
̂  22 ΋ղੳՄೳ
N
1
x̂ = arg min
∥y − As∥22 +  λ f(s)
{2
}
s∈ℝN
(α*, β*)ɿ min max 
α&gt;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Λ࢖ͬͯ‫ࢉ ܭ‬
ͷղ


# Page. 33

![Page Image](https://bcdn.docswell.com/page/5G753RWGJ4.jpg)

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


# Page. 34

![Page Image](https://bcdn.docswell.com/page/V9J2ZDQDER.jpg)

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


# Page. 35

![Page Image](https://bcdn.docswell.com/page/5DEYR2WMJM.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ʛະ஌ͷࡶԻ෼ࢄͷਪఆ
23/34
γϛϡϨʔγϣϯ৚݅
✓
‫ػࢉ ܭ‬γϛϡϨʔγϣϯͰɼະ஌ͷࡶ Ի෼ࢄͷਪఆਫ਼౓Λൺֱ
/. 4 &amp;ʢ /P S N B MJ [ F E .4 &amp; ʣ
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]


# Page. 36

![Page Image](https://bcdn.docswell.com/page/2VJND89378.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ʛະ஌ͷࡶԻ෼ࢄͷਪఆ
24/34
γϛϡϨʔγϣϯ݁Ռ
✓
σv2ʹରͯ͠΋ɼఏҊ ख๏͸ྑ͍ਪఆਫ਼౓Λୡ੒
ͲͷࡶԻ ෼ࢄ 
ఏҊख๏ʢ&quot;TZNQUPUJD 3FTJE VBM .BUD IJOHʣ
NMSE
/.
4&amp;
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


# Page. 37

![Page Image](https://bcdn.docswell.com/page/GYE9GK2PJ3.jpg)

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


# Page. 38

![Page Image](https://bcdn.docswell.com/page/5GE8VR5XED.jpg)

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


# Page. 39

![Page Image](https://bcdn.docswell.com/page/MLEL5KYN7R.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ
26/34
&quot; %. .ʢ &quot;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 ʣ
✓
&quot;%. .͕ର ৅ͱ͢Δ࠷ద Խ໰ ୊
ʢ ϕ1( ⋅ ), ϕ2( ⋅ ), Φʹ͸ͦΕͧΕ৚݅͋Γʣ
min {ϕ1(s) +  ϕ2(z) } subject to  Φs  =  z
s, z
ղ͖͍ͨ
࠷ద Խ ໰ ୊
ม‫ܗ‬
&quot; %. .Ͱ
ղ͚Δ‫ܗ‬
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
}


# Page. 40

![Page Image](https://bcdn.docswell.com/page/54JM32NQEW.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ
27/34
&quot; %. .ͷߋ ৽ ࣜ
✓
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


# Page. 41

![Page Image](https://bcdn.docswell.com/page/ZPJRQMDK79.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ
27/34
&quot; %. .ͷߋ ৽ ࣜ
✓
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


# Page. 42

![Page Image](https://bcdn.docswell.com/page/NPEX5V157X.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ
෦ ෼ ໰ ୊ͷղੳ
✓
28/34
&quot;%. .ͷߋ ৽ ࣜʹ‫·ؚ‬ΕΔ෦ ෼໰ ୊Λ$( .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 )ɿ͋Δ࠷దԽ ໰୊ͷղ


# Page. 43

![Page Image](https://bcdn.docswell.com/page/63EK6Q2RED.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ
&quot; %. .ͷղ ੳ ݁Ռͷ·ͱΊ
✓
29/34
&quot;%. .ͷߋ ৽ ࣜʹରԠ͢ΔεΧϥʔͷ֬ ཰ ա ఔΛಘΒΕΔ
s
(k+1)
ρ
1
2
= arg min
∥y − As∥2 +  ∥s − z (k) + w (k)∥22
2
{2
}
s∈ℝN
&quot;%. .ͷ
ߋ৽ࣜ
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 ͷ࣮ ‫ ݱ‬஋Λଟ਺ͭ͘Δ͜ͱͰɼ
&quot;%..ͷ֤൓ ෮Ͱͷਪ ఆ ஋  s (k)  ͷ઴ۙ తͳ‫ࠩ ޡ‬Λ༧ ଌ Մ ೳ


# Page. 44

![Page Image](https://bcdn.docswell.com/page/4L736P4G75.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ
30/34
γϛϡϨʔγϣϯ৚݅
✓
‫ػࢉ ܭ‬γϛϡϨʔγϣϯͰ
✦
&quot; %. .ͷ֤ ൓ ෮Ͱͷਪఆ ஋ s (k) ͷ.4&amp;ͷมԽ
✦
ཧ ࿦ղ ੳ ݁ Ռ͔ΒಘΒΕΔ઴ۙ త.4 &amp;ͷมԽ
ɹΛൺֱ
‫؍‬ଌ ཰  Δ = M/N = 0.7
M
y =
֬ ཰ 0.9 Ͱ 0 ɼ֬ ཰ 0.1 Ͱඪ ४Ψ΢ε෼ ෍ʹै͏
N
A
x + v
ࡶ Ի ෼ ࢄ σv2 = 0.0001
&quot; % ..ͷύϥϝʔλ ρ = 0.1
֤൓ ෮Ͱͷਪ ఆ஋s (k) (k = 0,1,2,…)


# Page. 45

![Page Image](https://bcdn.docswell.com/page/V87DVLQN7G.jpg)

$(.5Λ༻͍ͨཧ࿦ղੳͷԠ༻ʛ࠷దԽΞϧΰϦζϜͷղੳ
31/34
γϛϡϨʔγϣϯ݁Ռ
✓
N ͕े෼ େ͖͍৔ ߹ɼ
֤ ൓෮Ͱ࣮ࡍͷ. 4&amp;ͱ઴ ۙత .4&amp;͕͍ۙ஋ͱͳΔ
100
empirical (N = 50)
empirical (N = 100)
empirical (N = 500)
.
4&amp;
MSE
10°1
empirical (N = 1000)
prediction
asymptotic MSE of optimizer
10°2
࣮ ࡍͷ.4 &amp;
10°3
࠷ ద ղͷ઴ۙ త . 4&amp;ʹऩ ଋ
઴ ۙ త .4&amp;
10°4
0
࠷ ద ղͷ
઴ ۙత .4&amp;
5
10
15
20
number of iterations
&quot; %. .ͷ൓෮ճ਺
25
30


# Page. 46

![Page Image](https://bcdn.docswell.com/page/4VJPV2LNJ8.jpg)

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


# Page. 47

![Page Image](https://bcdn.docswell.com/page/L2EVZDQY7Q.jpg)

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


# Page. 48

![Page Image](https://bcdn.docswell.com/page/Z57G4YWWEL.jpg)

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


# Page. 49

![Page Image](https://bcdn.docswell.com/page/V4EQGM3QJP.jpg)

ࠓ‫ޙ‬ͷల๬ɾ·ͱΊ
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
ิॿ໰ ୊ʢ&quot;0
min max {∥e∥2 g 𝖳u − ∥u∥2 h 𝖳e + ξ(e, u)}
$ (. 5
1
2
✦ ઴ۙత . 4&amp;ɿ ∥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
✦ ࡶԻ෼ ࢄͷਪఆ
✦ ࠷దԽΞϧΰϦζϜͷղੳ
ʹ΋Ԡ༻Մೳ


