Compressed Sensing und der Rekonstruktions-Algorithmus ... · Vorteil ist, dass ein schneller...

Compressed Sensing und der Rekonstruktions-AlgorithmusNESTA

Abschlussvortrag

Claudia Nilles

TUM

25. März 2010

Claudia Nilles (TUM) Compressed Sensing und der Rekonstruktions-Algorithmus NESTA25. März 2010 2 / 43

Gliederung

1 Theoretische Grundlagen des Compressed SensingDünnbesetzte Signale und das AbtastproblemCharakterisierung der Messung und Eindeutigkeit der Lösung

2 Methodik des Compressed SensingRekonstruktionsstrategienÄquivalenz der Probleme P0 und P1Compressed Sensing für komprimierbare Signale und gestörte Daten

3 Lösen des MinimierungsproblemsAlgorithmus von NesterovAnwendung auf das Compressed Sensing ProblemAlgorithmus NESTA

4 Anwendung auf ein digitales BildKlassische KompressionCompressed Sensing

5 Résumé


Gliederung





5 Résumé


Dünnbesetztheit

Ein grundlegendes Prinzip für die Methode des Compressed Sensing ist dieForderung nach einer dünnbesetzten Darstellung des Signals.

De�nition (S-sparse)

Sei f ∈ Rn, Ψ = [ψ1, . . . , ψn] eine Orthonormalbasis des Rn und S ∈ N. Dannheiÿt f S-sparse bzgl. der Basis Ψ, falls f eine Linearkombination aus höchstens SBasisvektoren ist, d.h falls

f =n∑

i=1

xiψi bzw. kurz f = Ψx ,

wobei xi 6= 0 für höchstens S Koe�zienten.

`0-Norm: ‖x‖0

:=∑n

i=1 |x |0 = # Nichtnulleinträge von x , (wobei 00 := 0).


Abtastproblem

Formulierung des Abtastproblems als lineares Gleichungssystem:

Ψ ∈ Rn×n ONB des Rn, in der das Signal f S-sparse ist:

f = Ψx mit ‖x‖0≤ S .

Φ ∈ Rm×n, m < n Messmatrix mit Zeilen (ϕk) sodass

yk = 〈f , ϕk〉 , k = 1, ...,m bzw. y = Φf .

A := ΦΨ ∈ Rm×n.

Das Abtastproblem als unterbestimmtes lineares GleichungssystemRekonstruktion einer S-sparse Lösung x ∈ Rn mittels den m linearen Messungen,m < n,

y = Ax .

Eine S-sparse Lösung x0 heiÿt bestmöglich dünnbesetzt, falls

Ax0 = y und ‖x‖0> S ∀x 6= x0 mit Ax = y .


Abtastproblem

Formulierung des Abtastproblems als lineares Gleichungssystem:

Ψ ∈ Rn×n ONB des Rn, in der das Signal f S-sparse ist:

f = Ψx mit ‖x‖0≤ S .

Φ ∈ Rm×n, m < n Messmatrix mit Zeilen (ϕk) sodass

yk = 〈f , ϕk〉 , k = 1, ...,m bzw. y = Φf .

A := ΦΨ ∈ Rm×n.

Das Abtastproblem als unterbestimmtes lineares GleichungssystemRekonstruktion einer S-sparse Lösung x ∈ Rn mittels den m linearen Messungen,m < n,

y = Ax .

Eine S-sparse Lösung x0 heiÿt bestmöglich dünnbesetzt, falls

Ax0 = y und ‖x‖0> S ∀x 6= x0 mit Ax = y .


Gliederung





5 Résumé


Spark

De�nition (spark)

Für A ∈ Rm×n de�niere spark(A) ∈ N als die Kardinalität der kleinstenUntermenge linear abhängiger Spaltenvektoren von A.

Satz (Unschärferelation)

Sei A ∈ Rm×n und x1, x2 ∈ Rn, x1 6= x2 mit Ax1 = Ax2. Dann gilt

‖x1‖0 + ‖x2‖0 ≥ spark(A).

Korollar (Eindeutigkeit mittels spark)

Sei A ∈ Rm×n, y ∈ Rm und x ∈ Rn mit

Ax = y und ‖x‖0<

12spark(A),

dann ist x die bestmöglich dünnbesetzte Lösung des linearen Gleichungssystems.


Spark

De�nition (spark)




‖x1‖0 + ‖x2‖0 ≥ spark(A).




12spark(A),



Spark

De�nition (spark)




‖x1‖0 + ‖x2‖0 ≥ spark(A).




12spark(A),



Restricted Isometry Property

De�nition (Restricted Isometry Property (RIP))

Für S ∈ N de�niere die Isometrie-Konstante δS einer Matrix A ∈ Rm×n durch diekleinste Zahl, sodass

(1− δS) ‖x‖22≤ ‖Ax‖2

2≤ (1 + δS) ‖x‖2

2

für alle x ∈ Rn mit ‖x‖0≤ S gilt.

Ist δS < 1, dann erfüllt A die Restricted Isometry Property der Ordnung S .

Satz (Eindeutigkeit mittels RIP)

Sei A ∈ Rm×n und erfülle die RIP der Ordnung 2S mit Isometrie-Konstante δ2S .Sei y ∈ Rm und x ∈ Rn mit

y = Ax und ‖x‖0≤ S ,



Restricted Isometry Property

De�nition (Restricted Isometry Property (RIP))

Für S ∈ N de�niere die Isometrie-Konstante δS einer Matrix A ∈ Rm×n durch diekleinste Zahl, sodass

(1− δS) ‖x‖22≤ ‖Ax‖2

2≤ (1 + δS) ‖x‖2

2

für alle x ∈ Rn mit ‖x‖0≤ S gilt.

Ist δS < 1, dann erfüllt A die Restricted Isometry Property der Ordnung S .

Satz (Eindeutigkeit mittels RIP)

Sei A ∈ Rm×n und erfülle die RIP der Ordnung 2S mit Isometrie-Konstante δ2S .Sei y ∈ Rm und x ∈ Rn mit

y = Ax und ‖x‖0≤ S ,



Gliederung





5 Résumé


Rekonstruktionsstrategien

Angenommen es existiert eine bestmöglich dünnbesetzte Lösung x0 desunterbestimmten linearen Gleichungssystems

y = Ax .

Die direkte Methode x0 zu ermitteln entspricht dem Lösen folgendemMinimierungsproblems:

Problem P0

minx∈Rn

‖x‖0

u.d.N. y = Ax .

Dies ist ein NP-schweres Problem.


Dünnbesetzte Lösung

Abbildung: Darstellung der dünnbesetzten Lösung

x0 entspricht hierbei der Lösung des Problems P0

minx∈Rn

‖x‖0

u.d.N. y = Ax .


Geometrische Interpretation des `2-Minimierungsproblems

H = {x : Ax = y} x0x2

Abbildung: Darstellung der `2-Minimierung

x2 entspricht hierbei der Lösung des `2-Minimierungsproblems

minx∈Rn

‖x‖2

u.d.N. y = Ax .


Geometrische Interpretation des `1-Minimierungsproblems

H = {x : Ax = y} x0

Abbildung: Darstellung der `1-Minimierung

x0 entspricht hierbei der Lösung des `1-Minimierungsproblems P1

(P1) minx∈Rn

‖x‖1

u.d.N. y = Ax .


Gliederung





5 Résumé


Äquivalenz der Probleme P0 und P1

(P0) minx∈Rn

‖x‖0

u.d.N. y = Ax .

(P1) minx∈Rn

‖x‖1

u.d.N. y = Ax .

Äquivalenzsatz

Sei A ∈ Rm×n und erfülle die RIP der Ordnung 2S mit Isometrie-Konstante δ2S .Falls

δ2S <√2− 1

gilt, dann sind alle S-Sparse Lösungen des linearen Gleichungssystems y = Axgleich der Lösung des Problems P1. Somit ist x0 die Lösung des Problems P0genau dann, wenn x0 die Lösung des Problems P1 ist.


Äquivalenz der Probleme P0 und P1

(P0) minx∈Rn

‖x‖0

u.d.N. y = Ax .

(P1) minx∈Rn

‖x‖1

u.d.N. y = Ax .

Äquivalenzsatz

Sei A ∈ Rm×n und erfülle die RIP der Ordnung 2S mit Isometrie-Konstante δ2S .Falls

δ2S <√2− 1

gilt, dann sind alle S-Sparse Lösungen des linearen Gleichungssystems y = Axgleich der Lösung des Problems P1. Somit ist x0 die Lösung des Problems P0genau dann, wenn x0 die Lösung des Problems P1 ist.


Zufallsmatrizen

Gauÿsche Zufallsmatrix

Sei A ∈ Rm×n mit ai,j ∼ N(0, 1

m

).

Falls

m ≥ C

δ2

(S ln

( n

S

)+ ln

(1ε

)),

dann erfüllt die Matrix A die Restricted Isometry Property der Ordnung S miteiner Isometrie-Konstante δS ≤ δ mit einer Wahrscheinlichkeit von mindestens1− ε.

Diskrete Cosinus-TransformationSei A ∈ Rm×n, sodass die Zeilen zufällig gewählten Zeilen der diskretenCosinus-Transformation entsprechen.

In diesem Fall gelten ähnliche Ergebnisse wie im Fall der Gauÿschen Zufallsmatrix.Vorteil ist, dass ein schneller Algorithmus für die Matrix-Vektor-Multiplikationexistiert.


Beispielproblem

0 50 100−5

0

5

Abbildung: Dünnbesetztes Signal x0 ∈ R100 mit S = 10 Nichtnulleinträgen.


Beispielproblem

0 50 100−5

0

5


In rot ist die Lösung des `2-Minimierungsproblems abgebildet, wobei A ∈ R30×100 eine

Gauÿsche Zufallsmatrix. Diese Lösung erzielt keine sinnvolle Approximation des

dünnbesetzten Signals.


Beispielproblem

0 50 100−5

0

5


In rot ist die Lösung des Problems P1 abgebildet, wobei A ∈ R30×100 eine Gauÿsche

Zufallsmatrix. Die Lösung des `1-Minimierungsproblems ist exakt.


Gliederung





5 Résumé


Komprimierbare Signale und gestörte Daten

Zwei Fehlertypen:Komprimierbare Signale:x heiÿt S-compressible, falls höchstens S der Einträge xi groÿ und dierestlichen Einträge klein sind.

Messfehler:y = Ax + z , ‖z‖

2≤ ε.

Das `1-Minimierungsproblem wird zu

(P∗1) min ‖x‖

1u.d.N. ‖y − Ax‖

2≤ ε.


Compressed Sensing für verrauschte Daten

SatzSei A ∈ Rm×n und erfülle die RIP der Ordnung 2S mit Isometrie-Konstante

δ2S <√2− 1.

Sei y , z ∈ Rm und x ∈ Rn mit y = Ax + z , wobei ‖z‖2≤ ε und bezeichne x∗

1die

Lösung des Optimierungsproblems (P∗1). Dann gilt folgende Abschätzung

‖x∗1− x‖

2≤ C0

‖x − xS‖1√S

+ C1ε,

wobei xS dem Vektor entspricht, bei dem alle bis auf die gröÿten S Einträge aufNull gesetzt sind.


Gliederung





5 Résumé


Konvexes Optimierungsproblem

Problemstellung:

min f (x) u.d.N. x ∈ Q,

wobei

Q ⊂ Rn abgeschlossen und konvex.

f : Q → R konvex und di�erenzierbar. Zusätzlich sei der Gradient ∇fLipschitz-stetig auf Q mit Lipschitz-Konstante L, sodass

‖∇f (x)−∇f (y)‖2≤ L ‖x − y‖

2für alle x , y ∈ Q

gilt. Kurz: f ∈ F1

L(Q).


Methode von Nesterov

Sei f ∈ F1

L(Q), wobei Q⊂ Rn abgeschlossen und konvex.Sei p : Q → R streng konvex mit Konvexitätskonstante σ > 0.

AlgorithmusWähle Startpunkt x0 ∈ Q. Für k ≥ 0:

1 Bestimme ∇f (xk)

2 Berechne

yk = arg minx∈Q

{L

2‖x − xk‖22 + 〈∇f (xk), x − xk〉

}.

3 Berechne

zk = arg minx∈Q

{L

σp(x) +

k∑i=0

αi 〈∇f (xi ), x − xi 〉

}.

4 Aktualisiere xk durchxk = τkzk + (1− τk)yk .


Konvergenzsatz

SatzSei f ∈ F1

L(Q), wobei Q⊂ Rn abgeschlossen und konvex. Weiter sei p : Q→ Rstreng konvex mit Konvexitätskonstante σ. Zudem seien die Folgen (xk)k∈N,(yk)k∈N und (zk)k∈N durch den Algorithmus von Nesterov bestimmt und dieParameterfolgen (αk)k∈N und (τk)k∈N wie folgt de�niert:

αk =k + 12

und τk =2

k + 3.

Dann gilt für jedes k ≥ 0 die Abschätzung

f (yk)− f (x∗) ≤ 4 · L · p(x∗)

σ(k + 1)(k + 2),

wobei x∗ die optimale Lösung des Minimierungsproblems ist.


Gliederung





5 Résumé


Problemstellung

Compressed Sensing Problem (P∗1)

min ‖x‖1

u.d.N. x ∈ Q = {x ∈ Rn : ‖y − Ax‖2≤ ε}.

Problem: Die `1-Norm als Zielfunktion erfüllt nicht die gefordertenGlattheitsbedingungen des Algorithmus von Nesterov.

Abhilfe: Wende den Algorithmus von Nesterov auf eine hinreichend glatteApproximation der `1-Norm an.


Approximation an die `1-Norm

Huberfunktion

fµ(x) := maxu∈Qd

〈u, x〉 − µ

2‖u‖2

2mit Qd = {u ∈ Rn : ‖u‖∞ ≤ 1}.

Es gilt:

f0(x) = ‖x‖1und lim

µ→0

fµ(x) = ‖x‖1.

Für µ > 0 ist die Huberfunktion konvex und stetig di�erenzierbar mit

∇fµ(x)[i ] =

{µ−1x [i ], falls |x [i ]| < µ,

sgn(x [i ]), falls |x [i ]| ≥ µ.

Der Gradient ∇fµ(x) ist Lipschitz-stetig mit Lipschitz-Konstante Lµ = 1

µ .

Insgesamt gilt fµ ∈ F1

Lµ(Q) für µ > 0.


Huberfunktion

1 2 3 4−1−2−3−4

1

2

3

4

−1

µ = 1

µ = 0.5

µ = 0.2

ℓ1-Norm

Abbildung: `1-Norm und die Huberfunktion fµ für verschiedene Werte von µ im

Eindimensionalen. Letztere stellen eine hinreichend glatte Approximation an die `1-Normdar, um den Algorithmus von Nesterov auf diese anzuwenden.


Gliederung





5 Résumé


Algorithmus NESTA

Problemstellung:

min fµ(x) u.d.N. x ∈ Q = {x ∈ Rn : ‖y − Ax‖2≤ ε}.

Wende zur Problemlösung den Algorithmus von Nesterov an mit

p(x) = 1

2‖x − x0‖22.

Konvergenzsatz:

fµ(yk)− fµ(x∗µ) ≤4 · Lµ · p(x∗µ)

σ(k + 1)(k + 2)=

2∥∥x∗µ − x0

∥∥22

µ(k + 1)(k + 2),

wobei x∗µ = arg minx∈Q

fµ(x).

Beschleunigung mit veränderlichen Werten des Parameters µ und Anpassung derAbbildung p.


Numerische Untersuchungen

Rahmenbedingungen und Vorgehensweise:

Konstruktion eines dünnbesetzten Signals x ∈ Rn, mit n = 218 und S = n40

zufällig gewählten Nichtnulleinträgen, wobei |x(i)| ∈ [1, 105] (Hinzufügeneines Rauschens).

Messmatrix A ∈ Rm×n mit m = n8als zufällige Zeilen der diskreten

Cosinus-Transformation (Hinzufügen eines Störterms). Messungen sindgegeben durch: y = Ax + z .

Lösen des `1-Minimierungsproblems

min ‖x‖1

u.d.N. ‖Ax − y‖2≤ ε,

unter Verwendung des Algorithmus NESTA (µ = 0, 01).

⇒ 4-5 korrekte Dezimalstellen in der Lösung mit nur einigen hundert Iterationen.


Ergebnisse

Direkter Zusammenhang zwischen der Genauigkeit der Lösung und demParameter µ. Keine Feinabstimmung der weiteren Parameter notwendig.

Stabilität bezüglich Störungen in den Daten.

Konstante Ergebnisse in den Testreihen.


Gliederung





5 Résumé


Wavelet-Kompression anhand des Bildes LENA

Abbildung: Originalbild und komprimiertes Bild auf Grundlage der 5% gröÿten

Wavelet-Koe�zienten.


Gliederung





5 Résumé


Least-Square Lösung

Abbildung: Originalbild und Lösung des `2-Minimierungsproblems mit 50% der

Signallänge an Messungen.


Compressed Sensing

Abbildung: Lösung des `1-Minimierungsproblems mit 30%, 50% bzw. 70% der

Signallänge an Messungen.


Vergleich: Wavelet-Kompression und Compressed Sensing

Abbildung: Originalbild, Wavelet-Kompression und Lösung des `1-Minimierungsproblems

mit 50% der Signallänge an Messungen.


Résumé

Compressed Sensing ermöglicht die exakte Rekonstruktion von Signalen, diesich in einer bekannten Basis dünnbesetzt darstellen lassen, mit wesentlichweniger linearen Messungen als Freiheitsgrade.

Das Abtastproblem lässt sich als konvexes Optimierungsproblem formulieren.Somit ist ein akzeptabler Aufwand der Rekonstruktion garantiert.

Compressed Sensing genügt Wohlgestelltheitsanforderungen in dem Sinne,dass die Eindeutigkeit der Lösung und die Stabilität bezüglich Fehlern in denDaten gegeben ist.

Der Algorithmus NESTA eignet sich zur Rekonstruktion dünnbesetzterSignale und erzielt mit e�zientem Aufwand eine gute Rechengenauigkeit fürgroÿformatige Probleme.


Literatur

David L. Donoho, Michael Elad, Optimally sparse representation in general(nonorthogonal) dictionaries via `1-minimization, Proceedings of the NationalAcademy of Sciences of the United States of America (2003)

Emmanuel J. Candès, The restricted isometry property and its implicationsfor compressed sensing, Comptes Rendus Mathématique. Académie desSciences. Paris (2008)

Yurii Nesterov, Smooth minimization of non-smooth functions, A Publicationof the Mathematical Programming Society(2005)

Stephen Becker, Jerome Bobin and Emmanuel J.Candès, NESTA: a fast andaccurate �rst-order method for sparse recovery, California Institute ofTechnology (2009)


Date post:	18-Apr-2019
Category:	Documents
Upload:	dinhnguyet
View:	223 times
Download:	0 times

Compressed Sensing und der Rekonstruktions-Algorithmus ... · Vorteil ist, dass ein schneller...

Documents