Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Compressed Sensing

No description
by

Elisabeth Maier

on 23 January 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Compressed Sensing

Compressed Sensing

Martin Semisch
21/01/2013 Motivation 3 - CS-Fehlerkorrektur 4 - CS-Microarrays Anmerkungen Emmanuel Candès Terence
Tao Signal Messprozess Messung Dekodierung Anforderungen an das Signal Das Grundmodell Anforderungen an die Sensingmatrix Es ist möglich, beliebige k-sparse Signale mittels
C*k*log(n/k) linearer Messungen exakt zu
rekonstruieren. Gute Sensingmatrizen 1 - Theoretische Grundlagen Dekodierung l1-MAGIE: Das Signal x lässt sich aus den Messungen y einfach
als Lösung eines linearen Optimierungsproblems ermitteln.

Darüber hinaus sind gute Heuristiken bekannt (OMP, ...),
die das zugehörige l0-Problem lösen. Das DNA-Microarray Gruppe von Untersuchungs- und Analyseverfahren in der Biotechnologie
Ziel: Nachweis verschiedener Gene in einem Medium und Bestimmung ihrer Konzentration
Anwendungsgebiete: Trinkwasseranalyse, Genexpression Funktionsweise pro Spot eine spezifische, einsträngige DNA-Sequenz fixiert
Einsträngige, gemarkerte Proben-DNA wird hinzugegeben
Bindung der Proben-DNA an die Spot-DNA gemäß Schlüssel-Schloss-Prinzip
Abwaschen der Rest-DNA
Array scannen Mathematisches Modell Signal x entspricht dem Konzentrationenvektor der nachzuweisenden Gene in der Proben-DNA
Die Messmatrix A entspricht einer Diagonalmatrix
Die k-te Komponente von y entspricht der quantifizierten Leuchtintensität auf Spot k CS-Microarray Der BP-Algorithmus Mooresches Gesetz "Die Komplexität integrierter Schaltkreise mit minimalen Komponentenkosten verdoppelt sich alle ein bis zwei Jahre." Die Multi-Megapixel-Kamera Shannon/Nyquist http://myweb3.hs-harz.de/mkreyssig/af/pdf/NyquistShannon.pdf http://www.svetissa.de/wp-content/uploads/2012/09/Foto-2.jpg Um f(.) exakt rekonstruieren zu können,
muss man f(.) mit einer Rate abtasten,
die größer als das Doppelte der höchsten Frequenzkomponente ist. Wavelet-Transformation http://www.ams.org/samplings/math-history/hap7-pixel.pdf Single-Pixel-Kamera http://www.ams.org/samplings/math-history/hap7-pixel.pdf http://images.machinedesign.com/images/archive/71646getreadyjp_00000049584.jpg mathematisch? dauerhafte Speicherung und fehlerlose
Übertragung digitaler Daten Ziel der Informationstechnologie Kratzer auf CD
Störungen durch ein Magnetfeld bei der Mobilfunk-Übertragung
Brechung von Lichtsignalen am Glasfaserkabel 2 - CS und Bildverarbeitung Mathematisches Modell http://authors.library.caltech.edu/1378/1/CANieeetit05.pdf + exakte Rekonstruktion ist möglich, wenn die
Fehlerrate nicht zu hoch ist.
+ Betrag der einzelnen Fehlerkomponenten ist
irrelevant.
+ Anordnung der Fehlerkomponenten ist
irrelevant.

- Aufwand bei Dekodierung des Signals Eigenanteil der Diplomarbeit Bestimmung epsilon-optimaler Spielstrategien mit CS-Heuristiken
Statistische Aufarbeitung der Simulationsergebnisse GESUCHT:

ANREGUNGEN ZUR ANWENDUNG VON CS IN DEN WIRTSCHAFTSWISSENSCHAFTEN Literatur:

A. Cohen, W. Dahmen und R. DeVore: Compressed sensing and best k-term approximation, preprint, 2006.

E. Candès und T. Tao: Decoding by linear programming, IEEE Trans. Inform. Theory, 51(12):4203-4215.

M. Davenport: random observations on random observations: Sparse signal acquisition and processing, PhD thesis, Rice University, Houston, 2010.

M. Davenport, M. Duarte, Y. Eldar und G. Kutyniok: Introduction to compressed sensing, Kapitel in: Compressed Sensing: Theory and Applications, Cambridge University Press, 2012, Wien.

W. Dai, M. Sheikh, O. Milenkovic und R. Baraniuk: Compressive Sensing DNA Microarrays, preprint, 2008.

D. Mackenzie: Compressed Sensing Makes Every Pixel Count, What's Happening in the Math. Sciences, 7:114-127, 2008.


M. Duarte, M. Davenport, D. Takhar, J. Laska, T. Sun, K. Kelly und R. Baraniuk: Single-pixel imaging via compressive sampling, IEEE Sign. Proc. Mag., 25(2):83-91, 2008.

S. Sarvotham, D. Baron und R. Baraniuk: Compressed Sensing Reconstruction via Belief Propagation, preprint, 2006.

M. Semisch: Compressed Sensing in Theorie und Anwendung, Diplomarbeit, Friedrich-Schiller-Universität, Jena, 2012.

J. A. Tropp und A. C. Gilbert: Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit, IEEE Trans. Inform. Theory, 53(12):4655-4666, 2007. http://www-stat.stanford.edu/people/faculty/candes/index.html http://www.mozzochi.org/Tao/Tao1.html http://dsp.rice.edu/sites/dsp.rice.edu/files/cs/baraniukCSlecture07.pdf http://de.wikipedia.org/w/index.php?title=Datei:Microarray2.gif&filetimestamp=20070128215715 Brute Force noisy N 1 256x256 1300 CS-Messungen http://dsp.rice.edu/sites/dsp.rice.edu/files/cs/csCamera-SPMag-web.pdf http://dsp.rice.edu/sites/dsp.rice.edu/files/cs/csCamera-SPMag-web.pdf http://myweb3.hs-harz.de/mkreyssig/af/pdf/NyquistShannon.pdf Quelle: YouTube Orthogonal Matching Pursuit (OMP)
nach Gilbert/Tropp http://dsp.rice.edu/sites/dsp.rice.edu/files/cs/CSMProbeDesign02.pdf
Full transcript