Dagstuhl Seminar Proceedings, Volume 8492



Publication Details

  • published at: 2009-02-24
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
08492 Abstracts Collection – Structured Decompositions and Efficient Algorithms

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


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.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
08492 Executive Summary – Structured Decompositions and Efficient Algorithms

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


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.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
A Weighted Average of Sparse Representations is Better than the Sparsest One Alone

Authors: Michael Elad and Irad Yavneh


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.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}
}
Document
An open question on the existence of Gabor frames in general linear position

Authors: Felix Krahmer, Götz E. Pfander, and Peter Rashkov


Abstract
Uncertainty principles for functions defined on finite Abelian groups generally relate the cardinality of a function to the cardinality of its Fourier transform. We examine how the cardinality of a function is related to the cardinality of its short--time Fourier transform. We illustrate that for some cyclic groups of small order, both, the Fourier and the short--time Fourier case, show a remarkable resemblance. We pose the question whether this correspondence holds for all cyclic groups.

Cite as

Felix Krahmer, Götz E. Pfander, and Peter Rashkov. An open question on the existence of Gabor frames in general linear position. In Structured Decompositions and Efficient Algorithms. Dagstuhl Seminar Proceedings, Volume 8492, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{krahmer_et_al:DagSemProc.08492.4,
  author =	{Krahmer, Felix and Pfander, G\"{o}tz E. and Rashkov, Peter},
  title =	{{An open question on the existence of Gabor frames  in general linear position}},
  booktitle =	{Structured Decompositions and Efficient Algorithms},
  pages =	{1--7},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.08492.4},
  URN =		{urn:nbn:de:0030-drops-18848},
  doi =		{10.4230/DagSemProc.08492.4},
  annote =	{Keywords: Gabor systems, erasure channels, time--frequency dictionaries, short--time Fourier transform, uncertainty principle.}
}
Document
Arbitrary Shrinkage Rules for Approximation Schemes with Sparsity Constraints

Authors: Martin Ehler and Simone Geisel


Abstract
Finding a sparse representation of a possibly noisy signal is a common problem in signal representation and processing. It can be modeled as a variational minimization with $ell_ au$-sparsity constraints for $ au<1$. Applications whose computation time is crucial require fast algorithms for this minimization. However, there are no fast methods for finding the exact minimizer, and to circumvent this limitation, we consider minimization up to a constant factor. We verify that arbitrary shrinkage rules provide closed formulas for such minimizers, and we introduce a new shrinkage strategy, which is adapted to $ au<1$.

Cite as

Martin Ehler and Simone Geisel. Arbitrary Shrinkage Rules for Approximation Schemes with Sparsity Constraints. In Structured Decompositions and Efficient Algorithms. Dagstuhl Seminar Proceedings, Volume 8492, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{ehler_et_al:DagSemProc.08492.5,
  author =	{Ehler, Martin and Geisel, Simone},
  title =	{{Arbitrary Shrinkage Rules for Approximation Schemes with Sparsity Constraints}},
  booktitle =	{Structured Decompositions and Efficient Algorithms},
  pages =	{1--12},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.08492.5},
  URN =		{urn:nbn:de:0030-drops-18816},
  doi =		{10.4230/DagSemProc.08492.5},
  annote =	{Keywords: Frames, shrinkage, variational problems, sparse approximation}
}
Document
Pseudospectral Fourier reconstruction with IPRM

Authors: Karlheinz Gröchenig and Tomasz Hrycak


Abstract
We generalize the Inverse Polynomial Reconstruction Method (IPRM) for mitigation of the Gibbs phenomenon by reconstructing a function as an algebraic polynomial of degree $n-1$ from the function's $m$ lowest Fourier coefficients ($m ge n$). We compute approximate Legendre coefficients of the function by solving a linear least squares problem, and we show that the condition number of the problem does not exceed $sqrtfrac{m}{{m-alpha_0 n^2}}$, where $alpha_0 = frac{4sqrt{2}}{pi^2} = 0.573 ldots$. Consequently, whenever mbox{$m ge n^2$,} the convergence rate of the modified IPRM for an analytic function is root exponential on the whole interval of definition. Stability and accuracy of the proposed algorithm are validated with numerical experiments.

Cite as

Karlheinz Gröchenig and Tomasz Hrycak. Pseudospectral Fourier reconstruction with IPRM. In Structured Decompositions and Efficient Algorithms. Dagstuhl Seminar Proceedings, Volume 8492, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{grochenig_et_al:DagSemProc.08492.6,
  author =	{Gr\"{o}chenig, Karlheinz and Hrycak, Tomasz},
  title =	{{Pseudospectral Fourier reconstruction with IPRM}},
  booktitle =	{Structured Decompositions and Efficient Algorithms},
  pages =	{1--3},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.08492.6},
  URN =		{urn:nbn:de:0030-drops-18830},
  doi =		{10.4230/DagSemProc.08492.6},
  annote =	{Keywords: IPRM, Fourier series, inverse methods, pseudospectral methods}
}
Document
Representation of Operators in the Time-Frequency Domain and Generalzed Gabor Multipliers

Authors: Monika Dörfler and Bruno Torrésani


Abstract
Starting from a general operator representation in the time-frequency domain, this paper addresses the problem of approximating linear operators by operators that are diagonal or band-diagonal with respect to Gabor frames. A haracterization of operators that can be realized as Gabor multipliers is given and necessary conditions for the existence of (Hilbert-Schmidt) optimal Gabor multiplier approximations are discussed and an efficient method for the calculation of an operator's best approximation by a Gabor multiplier is derived. The spreading function of Gabor multipliers yields new error estimates for these approximations. Generalizations (multiple Gabor multipliers) are introduced for better approximation of overspread operators. The Riesz property of the projection operators involved in generalized Gabor multipliers is characterized, and a method for obtaining an operator's best approximation by a multiple Gabor multiplier is suggested. Finally, it is shown that in certain situations, generalized Gabor multipliers reduce to a finite sum of regular Gabor multipliers with adapted windows.

Cite as

Monika Dörfler and Bruno Torrésani. Representation of Operators in the Time-Frequency Domain and Generalzed Gabor Multipliers. In Structured Decompositions and Efficient Algorithms. Dagstuhl Seminar Proceedings, Volume 8492, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{dorfler_et_al:DagSemProc.08492.7,
  author =	{D\"{o}rfler, Monika and Torr\'{e}sani, Bruno},
  title =	{{Representation of Operators in the Time-Frequency Domain and Generalzed Gabor Multipliers}},
  booktitle =	{Structured Decompositions and Efficient Algorithms},
  pages =	{1--28},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.08492.7},
  URN =		{urn:nbn:de:0030-drops-18808},
  doi =		{10.4230/DagSemProc.08492.7},
  annote =	{Keywords: Operator approximation, generalized Gabor multipliers, spreading function, twisted convolution}
}
Document
Sparse Reconstructions for Inverse PDE Problems

Authors: Thorsten Raasch


Abstract
We are concerned with the numerical solution of linear parameter identification problems for parabolic PDE, written as an operator equation $Ku=f$. The target object $u$ is assumed to have a sparse expansion with respect to a wavelet system $Psi={psi_lambda}$ in space-time, being equivalent to a priori information on the regularity of $u=mathbf u^ opPsi$ in a certain scale of Besov spaces $B^s_{p,p}$. For the recovery of the unknown coefficient array $mathbf u$, we miminize a Tikhonov-type functional begin{equation*} min_{mathbf u}|Kmathbf u^ opPsi-f^delta|^2+alphasum_{lambda}omega_lambda|u_lambda|^p end{equation*} by an associated thresholded Landweber algorithm, $f^delta$ being a noisy version of $f$. Since any application of the forward operator $K$ and its adjoint involves the numerical solution of a PDE, perturbed versions of the iteration have to be studied. In particular, for reasons of efficiency, adaptive applications of $K$ and $K^*$ are indispensable cite{Ra07}. By a suitable choice of the respective tolerances and stopping criteria, also the adaptive iteration could recently be shown to have regularizing properties cite{BoMa08a} for $p>1$. Moreover, the sequence of iterates linearly converges to the minimizer of the functional, a result which can also be proved for the special case $p=1$, see [DaFoRa08]. We illustrate the performance of the resulting method by numerical computations for one- and two-dimensional inverse heat conduction problems. References: [BoMa08a] T. Bonesky and P. Maass, Iterated soft shrinkage with adaptive operator evaluations, Preprint, 2008 [DaFoRa08] S. Dahlke, M. Fornasier, and T. Raasch, Multiscale Preconditioning for Adaptive Sparse Optimization, in preparation, 2008 [Ra07] T.~Raasch, Adaptive wavelet and frame schemes for elliptic and parabolic equations, Dissertation, Philipps-Universit"at Marburg, 2007

Cite as

Thorsten Raasch. Sparse Reconstructions for Inverse PDE Problems. In Structured Decompositions and Efficient Algorithms. Dagstuhl Seminar Proceedings, Volume 8492, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{raasch:DagSemProc.08492.8,
  author =	{Raasch, Thorsten},
  title =	{{Sparse Reconstructions for Inverse PDE Problems}},
  booktitle =	{Structured Decompositions and Efficient Algorithms},
  pages =	{1--8},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.08492.8},
  URN =		{urn:nbn:de:0030-drops-18784},
  doi =		{10.4230/DagSemProc.08492.8},
  annote =	{Keywords: Adaptivity, sparse reconstructions, l1 minimization, parameter identification}
}
Document
The Continuous Shearlet Transform in Arbitrary Space Dimensions

Authors: Stephan Dahlke, Gabriele Steidl, and Gerd Teschke


Abstract
This note is concerned with the generalization of the continuous shearlet transform to higher dimensions. Similar to the two-dimensional case, our approach is based on translations, anisotropic dilations and specific shear matrices. We show that the associated integral transform again originates from a square-integrable representation of a specific group, the full $n$-variate shearlet group. Moreover, we verify that by applying the coorbit theory, canonical scales of smoothness spaces and associated Banach frames can be derived. We also indicate how our transform can be used to characterize singularities in signals.

Cite as

Stephan Dahlke, Gabriele Steidl, and Gerd Teschke. The Continuous Shearlet Transform in Arbitrary Space Dimensions. In Structured Decompositions and Efficient Algorithms. Dagstuhl Seminar Proceedings, Volume 8492, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{dahlke_et_al:DagSemProc.08492.9,
  author =	{Dahlke, Stephan and Steidl, Gabriele and Teschke, Gerd},
  title =	{{The Continuous Shearlet  Transform in Arbitrary Space Dimensions}},
  booktitle =	{Structured Decompositions and Efficient Algorithms},
  pages =	{1--7},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.08492.9},
  URN =		{urn:nbn:de:0030-drops-19216},
  doi =		{10.4230/DagSemProc.08492.9},
  annote =	{Keywords: }
}
Document
Time-Frequency Analysis and PDE's

Authors: Anita Tabacco


Abstract
We study the action on modulation spaces of Fourier multipliers with symbols $e^{imu(xi)}$, for real-valued functions $mu$ having unbounded second derivatives. We show that if $mu$ satisfies the usual symbol estimates of order $alphageq2$, or if $mu$ is a positively homogeneous function of degree $alpha$, the corresponding Fourier multiplier is bounded as an operator between the weighted modulation spaces $mathcal{M}^{p,q}_delta$ and $mathcal{M}^{p,q}$, for every $1leq p,qleqinfty$ and $deltageq d(alpha-2)|frac{1}{p}-frac{1}{2}|$. Here $delta$ represents the loss of derivatives. The above threshold is shown to be sharp for {it all} homogeneous functions $mu$ whose Hessian matrix is non-degenerate at some point.

Cite as

Anita Tabacco. Time-Frequency Analysis and PDE's. In Structured Decompositions and Efficient Algorithms. Dagstuhl Seminar Proceedings, Volume 8492, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{tabacco:DagSemProc.08492.10,
  author =	{Tabacco, Anita},
  title =	{{Time-Frequency Analysis and PDE's}},
  booktitle =	{Structured Decompositions and Efficient Algorithms},
  pages =	{1--4},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.08492.10},
  URN =		{urn:nbn:de:0030-drops-18792},
  doi =		{10.4230/DagSemProc.08492.10},
  annote =	{Keywords: Fourier multipliers, modulation spaces, short-time Fourier transform}
}

Filters


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