DROPS

Document

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.9

The Continuous Shearlet Transform in Arbitrary Space Dimensions

Authors: Stephan Dahlke, Gabriele Steidl, and Gerd Teschke

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

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-dev.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

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}
}

Document

DOI: 10.4230/DagSemProc.08492.4

An open question on the existence of Gabor frames in general linear position

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

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

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-dev.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

DOI: 10.4230/DagSemProc.08492.5

Arbitrary Shrinkage Rules for Approximation Schemes with Sparsity Constraints

Authors: Martin Ehler and Simone Geisel

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

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-dev.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

DOI: 10.4230/DagSemProc.08492.6

Pseudospectral Fourier reconstruction with IPRM

Authors: Karlheinz Gröchenig and Tomasz Hrycak

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

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-dev.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

DOI: 10.4230/DagSemProc.08492.7

Representation of Operators in the Time-Frequency Domain and Generalzed Gabor Multipliers

Authors: Monika Dörfler and Bruno Torrésani

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

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-dev.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

DOI: 10.4230/DagSemProc.08492.8

Sparse Reconstructions for Inverse PDE Problems

Authors: Thorsten Raasch

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

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-dev.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

DOI: 10.4230/DagSemProc.08492.10

Time-Frequency Analysis and PDE's

Authors: Anita Tabacco

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

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-dev.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}
}

Document

DOI: 10.4230/DagSemProc.06391.1

06391 Abstracts Collection – Algorithms and Complexity for Continuous Problems

Authors: Stephan Dahlke, Klaus Ritter, Ian H. Sloan, and Joseph F. Traub

Published in: Dagstuhl Seminar Proceedings, Volume 6391, Algorithms and Complexity for Continuous Problems (2007)

Abstract

From 24.09.06 to 29.09.06, the Dagstuhl Seminar 06391 ``Algorithms and Complexity for Continuous Problems'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar 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, Klaus Ritter, Ian H. Sloan, and Joseph F. Traub. 06391 Abstracts Collection – Algorithms and Complexity for Continuous Problems. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 6391, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{dahlke_et_al:DagSemProc.06391.1,
  author =	{Dahlke, Stephan and Ritter, Klaus and Sloan, Ian H. and Traub, Joseph F.},
  title =	{{06391 Abstracts Collection – Algorithms and Complexity for Continuous Problems}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6391},
  editor =	{Stephan Dahlke and Klaus Ritter and Ian H. Sloan and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06391.1},
  URN =		{urn:nbn:de:0030-drops-8782},
  doi =		{10.4230/DagSemProc.06391.1},
  annote =	{Keywords: Computational complexity, partial information, high-dimensional problems, operator equations, non-linear approximation, quantum computation, stochastic computation, ill posed-problems}
}

Document

DOI: 10.4230/DagSemProc.06391.2

Real Computational Universality: The Word Problem for a class of groups with infinite presentation

Authors: Klaus Meer and Martin Ziegler

Published in: Dagstuhl Seminar Proceedings, Volume 6391, Algorithms and Complexity for Continuous Problems (2007)

Abstract

In this talk we introduce a class of groups represented as quotient groups of some free groups generated by infinitely many elements and certain normal subgroups. We show that the related word problem is universal in the Blum-Shub-Smale model of computation, i.e. it has the same difficulty as the real Halting Problem. This is the first natural example of a problem with this property. The work has been done jointly with Martin Ziegler.

Cite as

Klaus Meer and Martin Ziegler. Real Computational Universality: The Word Problem for a class of groups with infinite presentation. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 6391, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{meer_et_al:DagSemProc.06391.2,
  author =	{Meer, Klaus and Ziegler, Martin},
  title =	{{Real Computational Universality: The Word Problem for a class of groups with infinite presentation}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6391},
  editor =	{Stephan Dahlke and Klaus Ritter and Ian H. Sloan and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06391.2},
  URN =		{urn:nbn:de:0030-drops-8773},
  doi =		{10.4230/DagSemProc.06391.2},
  annote =	{Keywords: Computational group theory, word problem, Blum-Shub-Smale model}
}

Document

DOI: 10.4230/DagSemProc.06391.3

Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries

Authors: Howard Barnum

Published in: Dagstuhl Seminar Proceedings, Volume 6391, Algorithms and Complexity for Continuous Problems (2007)

Abstract

Generalizing earlier work characterizing the quantum query complexity of computing a function of an unknown classical ``black box'' function drawn from some set of such black box functions, we investigate a more general quantum query model in which the goal is to compute functions of $N imes N$ ``black box'' unitary matrices drawn from a set of such matrices, a problem with applications to determining properties of quantum physical systems. We characterize the existence of an algorithm for such a query problem, with given query and error, as equivalent to the feasibility of a certain set of semidefinite programming constraints, or equivalently the infeasibility of a dual of these constraints, which we construct. Relaxing the primal constraints to correspond to mere pairwise near-orthogonality of the final states of a quantum computer, conditional on the various black-box inputs, rather than bounded-error distinguishability, we obtain a relaxed primal program the feasibility of whose dual still implies the nonexistence of a quantum algorithm. We use this to obtain a generalization, to our not-necessarily-commutative setting, of the ``spectral adversary method'' for quantum query lower bounds.

Cite as

Howard Barnum. Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 6391, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{barnum:DagSemProc.06391.3,
  author =	{Barnum, Howard},
  title =	{{Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6391},
  editor =	{Stephan Dahlke and Klaus Ritter and Ian H. Sloan and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06391.3},
  URN =		{urn:nbn:de:0030-drops-8769},
  doi =		{10.4230/DagSemProc.06391.3},
  annote =	{Keywords: Quantum query complexity semidefinite programming}
}

Document

DOI: 10.4230/DagSemProc.04401.12

Optimal Approximation of Elliptic Problems by Linear and Nonlinear Mappings

Authors: Erich Novak, Stephan Dahlke, and Winfried Sickel

Published in: Dagstuhl Seminar Proceedings, Volume 4401, Algorithms and Complexity for Continuous Problems (2005)

Abstract

We study the optimal approximation of the solution of an operator equation Au=f by linear mappings of rank n and compare this with the best n-term approximation with respect to an optimal Riesz basis. We consider worst case errors, where f is an element of the unit ball of a Hilbert space. We apply our results to boundary value problems for elliptic PDEs on an arbitrary bounded Lipschitz domain. Here we prove that approximation by linear mappings is as good as the best n-term approximation with respect to an optimal Riesz basis. Our results are concerned with approximation, not with computation. Our goal is to understand better the possibilities of nonlinear approximation.

Cite as

Erich Novak, Stephan Dahlke, and Winfried Sickel. Optimal Approximation of Elliptic Problems by Linear and Nonlinear Mappings. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{novak_et_al:DagSemProc.04401.12,
  author =	{Novak, Erich and Dahlke, Stephan and Sickel, Winfried},
  title =	{{Optimal Approximation of Elliptic Problems by Linear and Nonlinear Mappings}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4401},
  editor =	{Thomas M\"{u}ller-Gronbach and Erich Novak and Knut Petras and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04401.12},
  URN =		{urn:nbn:de:0030-drops-1471},
  doi =		{10.4230/DagSemProc.04401.12},
  annote =	{Keywords: elliptic operator equation , worst case error , linear approximation method , nonlinear approximation method , best n-term approximation Bernstein widths , manifold widths}
}

16 Search Results for "Dahlke, Stephan"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message