5 Search Results for "Elad, Michael"

Document
DOI: 10.4230/LIPIcs.ICALP.2016.40
Online Semidefinite Programming

Authors: Noa Elad, Satyen Kale, and Joseph (Seffi) Naor

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We consider semidefinite programming through the lens of online algorithms - what happens if not all input is given at once, but rather iteratively? In what way does it make sense for a semidefinite program to be revealed? We answer these questions by defining a model for online semidefinite programming. This model can be viewed as a generalization of online coveringpacking linear programs, and it also captures interesting problems from quantum information theory. We design an online algorithm for semidefinite programming, utilizing the online primaldual method, achieving a competitive ratio of O(log(n)), where n is the number of matrices in the primal semidefinite program. We also design an algorithm for semidefinite programming with box constraints, achieving a competitive ratio of O(log F*), where F* is a sparsity measure of the semidefinite program. We conclude with an online randomized rounding procedure.
Cite as

Noa Elad, Satyen Kale, and Joseph (Seffi) Naor. Online Semidefinite Programming. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{elad_et_al:LIPIcs.ICALP.2016.40,
  author =	{Elad, Noa and Kale, Satyen and Naor, Joseph (Seffi)},
  title =	{{Online Semidefinite Programming}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{40:1--40:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.40},
  URN =		{urn:nbn:de:0030-drops-63205},
  doi =		{10.4230/LIPIcs.ICALP.2016.40},
  annote =	{Keywords: online algorithms, semidefinite programming, primal-dual}
}
Document
DOI: 10.4230/DagRep.1.1.108
Sparse Representations and Efficient Sensing of Data (Dagstuhl Seminar 11051)

Authors: Stephan Dahlke, Michael Elad, Yonina Eldar, Gitta Kutyniok, and Gerd Teschke

Published in: Dagstuhl Reports, Volume 1, Issue 1 (2011)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 11051 ``Sparse Representations and Efficient Sensing of Data''. The scope of the seminar was twofold. First, we wanted to elaborate the state of the art in the field of sparse data representation and corresponding efficient data sensing methods. Second, we planned to explore and analyze the impact of methods in computational science disciplines that serve these fields, and the possible resources allocated for industrial applications.
Cite as

Stephan Dahlke, Michael Elad, Yonina Eldar, Gitta Kutyniok, and Gerd Teschke. Sparse Representations and Efficient Sensing of Data (Dagstuhl Seminar 11051). In Dagstuhl Reports, Volume 1, Issue 1, pp. 108-127, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{dahlke_et_al:DagRep.1.1.108,
  author =	{Dahlke, Stephan and Elad, Michael and Eldar, Yonina and Kutyniok, Gitta and Teschke, Gerd},
  title =	{{Sparse Representations and Efficient Sensing of Data (Dagstuhl Seminar 11051)}},
  pages =	{108--127},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{1},
  editor =	{Dahlke, Stephan and Elad, Michael and Eldar, Yonina and Kutyniok, Gitta and Teschke, Gerd},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.1.1.108},
  URN =		{urn:nbn:de:0030-drops-31507},
  doi =		{10.4230/DagRep.1.1.108},
  annote =	{Keywords: Efficient signal sensing schemes, sparse signal representations, efficient signal reconstruction algorithms, impact of the methods in neighboring research fields and applications}
}
Document
DOI: 10.4230/DagSemProc.08492.1
08492 Abstracts Collection – Structured Decompositions and Efficient Algorithms

Authors: Stephan Dahlke, Ingrid Daubechies, Michael Elad, Gitta Kutyniok, and Gerd Teschke

Published in: Dagstuhl Seminar Proceedings, Volume 8492, Structured Decompositions and Efficient Algorithms (2009)

Abstract
From 30.11. to 05.12.2008, the Dagstuhl Seminar 08492 ``Structured Decompositions and Efficient Algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Stephan Dahlke, Ingrid Daubechies, Michael Elad, Gitta Kutyniok, and Gerd Teschke. 08492 Abstracts Collection – Structured Decompositions and Efficient Algorithms. In Structured Decompositions and Efficient Algorithms. Dagstuhl Seminar Proceedings, Volume 8492, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{dahlke_et_al:DagSemProc.08492.1,
  author =	{Dahlke, Stephan and Daubechies, Ingrid and Elad, Michael and Kutyniok, Gitta and Teschke, Gerd},
  title =	{{08492 Abstracts Collection – Structured Decompositions and Efficient Algorithms}},
  booktitle =	{Structured Decompositions and Efficient Algorithms},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8492},
  editor =	{Stephan Dahlke and Ingrid Daubechies and Michal Elad and Gitta Kutyniok and Gerd Teschke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08492.1},
  URN =		{urn:nbn:de:0030-drops-18860},
  doi =		{10.4230/DagSemProc.08492.1},
  annote =	{Keywords: Sparse signal representation, optimal signal reconstruction, approximation, compression}
}
Document
DOI: 10.4230/DagSemProc.08492.2
08492 Executive Summary – Structured Decompositions and Efficient Algorithms

Authors: Stephan Dahlke, Ingrid Daubechies, Michael Elad, Gitta Kutyniok, and Gerd Teschke

Published in: Dagstuhl Seminar Proceedings, Volume 8492, Structured Decompositions and Efficient Algorithms (2009)

Abstract
New emerging technologies such as high-precision sensors or new MRI machines drive us towards a challenging quest for new, more effective, and more daring mathematical models and algorithms. Therefore, in the last few years researchers have started to investigate different methods to efficiently represent or extract relevant information from complex, high dimensional and/or multimodal data. Efficiently in this context means a representation that is linked to the features or characteristics of interest, thereby typically providing a sparse expansion of such. Besides the construction of new and advanced ansatz systems the central question is how to design algorithms that are able to treat complex and high dimensional data and that efficiently perform a suitable approximation of the signal. One of the main challenges is to design new sparse approximation algorithms that would ideally combine, with an adjustable tradeoff, two properties: a provably good `quality' of the resulting decomposition under mild assumptions on the analyzed sparse signal, and numerically efficient design.
Cite as

Stephan Dahlke, Ingrid Daubechies, Michael Elad, Gitta Kutyniok, and Gerd Teschke. 08492 Executive Summary – Structured Decompositions and Efficient Algorithms. In Structured Decompositions and Efficient Algorithms. Dagstuhl Seminar Proceedings, Volume 8492, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{dahlke_et_al:DagSemProc.08492.2,
  author =	{Dahlke, Stephan and Daubechies, Ingrid and Elad, Michael and Kutyniok, Gitta and Teschke, Gerd},
  title =	{{08492 Executive Summary – Structured Decompositions and Efficient Algorithms }},
  booktitle =	{Structured Decompositions and Efficient Algorithms},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8492},
  editor =	{Stephan Dahlke and Ingrid Daubechies and Michal Elad and Gitta Kutyniok and Gerd Teschke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08492.2},
  URN =		{urn:nbn:de:0030-drops-18851},
  doi =		{10.4230/DagSemProc.08492.2},
  annote =	{Keywords: Sparse signal representation, optimal signal reconstruction, approximation, compression}
}
Document
DOI: 10.4230/DagSemProc.08492.3
A Weighted Average of Sparse Representations is Better than the Sparsest One Alone

Authors: Michael Elad and Irad Yavneh

Published in: Dagstuhl Seminar Proceedings, Volume 8492, Structured Decompositions and Efficient Algorithms (2009)

Abstract
Cleaning of noise from signals is a classical and long-studied problem in signal processing. Algorithms for this task necessarily rely on an a-priori knowledge about the signal characteristics, along with information about the noise properties. For signals that admit sparse representations over a known dictionary, a commonly used denoising technique is to seek the sparsest representation that synthesizes a signal close enough to the corrupted one. As this problem is too complex in general, approximation methods, such as greedy pursuit algorithms, are often employed. In this line of reasoning, we are led to believe that detection of the sparsest representation is key in the success of the denoising goal. Does this mean that other competitive and slightly inferior sparse representations are meaningless? Suppose we are served with a group of competing sparse representations, each claiming to explain the signal differently. Can those be fused somehow to lead to a better result? Surprisingly, the answer to this question is positive; merging these representations can form a more accurate, yet dense, estimate of the original signal even when the latter is known to be sparse. In this paper we demonstrate this behavior, propose a practical way to generate such a collection of representations by randomizing the Orthogonal Matching Pursuit (OMP) algorithm, and produce a clear analytical justification for the superiority of the associated Randomized OMP (RandOMP) algorithm. We show that while the Maximum a-posterior Probability (MAP) estimator aims to find and use the sparsest representation, the Minimum Mean-Squared-Error (MMSE) estimator leads to a fusion of representations to form its result. Thus, working with an appropriate mixture of candidate representations, we are surpassing the MAP and tending towards the MMSE estimate, and thereby getting a far more accurate estimation, especially at medium and low SNR.
Cite as

Michael Elad and Irad Yavneh. A Weighted Average of Sparse Representations is Better than the Sparsest One Alone. In Structured Decompositions and Efficient Algorithms. Dagstuhl Seminar Proceedings, Volume 8492, pp. 1-35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{elad_et_al:DagSemProc.08492.3,
  author =	{Elad, Michael and Yavneh, Irad},
  title =	{{A Weighted Average of Sparse Representations is Better than the Sparsest One Alone}},
  booktitle =	{Structured Decompositions and Efficient Algorithms},
  pages =	{1--35},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8492},
  editor =	{Stephan Dahlke and Ingrid Daubechies and Michal Elad and Gitta Kutyniok and Gerd Teschke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08492.3},
  URN =		{urn:nbn:de:0030-drops-18828},
  doi =		{10.4230/DagSemProc.08492.3},
  annote =	{Keywords: Sparse representations, MMSE, MAP, mathcing pursuit}
}
  • Refine by Author
  • 4 Elad, Michael
  • 3 Dahlke, Stephan
  • 3 Kutyniok, Gitta
  • 3 Teschke, Gerd
  • 2 Daubechies, Ingrid
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 Sparse signal representation
  • 2 approximation
  • 2 compression
  • 2 optimal signal reconstruction
  • 1 Efficient signal sensing schemes
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 3 2009
  • 1 2011
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact