The Experts below are selected from a list of 92589 Experts worldwide ranked by ideXlab platform
Michael Unser - One of the best experts on this subject based on the ideXlab platform.
-
Continuous Domain signal reconstruction using l_ p norm regularization
IEEE Transactions on Signal Processing, 2020Co-Authors: Pakshal Bohra, Michael UnserAbstract:We focus on the generalized-interpolation problem. There, one reconstructs Continuous-Domain signals that honor discrete data constraints. This problem is infinite-dimensional and ill-posed. We make it well-posed by imposing that the solution balances data fidelity and some $L_{p}$ -norm regularization. More specifically, we consider $p\geq 1$ and the multi-order derivative regularization operator ${\mathrm{L}}={\mathrm{D}}^{N_{0}}$ . We reformulate the regularized problem exactly as a finite-dimensional one by restricting the search space to a suitable space of polynomial splines with knots on a uniform grid. Our splines are represented in a B-spline basis, which results in a well-conditioned discretization. For a sufficiently fine grid, our search space contains functions that are arbitrarily close to the solution of the underlying problem where our constraint that the solution must live in a spline space would have been lifted. This remarkable property is due to the approximation power of splines. We use the alternating-direction method of multipliers along with a multiresolution strategy to compute our solution. We present numerical results for spatial and Fourier interpolation. Through our experiments, we investigate features induced by the $L_{p}$ -norm regularization, namely, sparsity, regularity, and oscillatory behavior.
-
Hybrid-Spline Dictionaries for Continuous-Domain Inverse Problems
IEEE Transactions on Signal Processing, 2019Co-Authors: Thomas Debarre, Shayan Aziznejad, Michael UnserAbstract:We study one-dimensional Continuous-Domain inverse problems with multiple generalized total-variation regularization, which involves the joint use of several regularization operators. Our starting point is a new representer theorem that states that such inverse problems have hybrid-spline solutions with a total sparsity bounded by the number of measurements. We show that such Continuous-Domain problems can be discretized in an exact way by using a union of B-spline dictionary bases matched to the regularization operators. We then propose a multiresolution algorithm that selects an appropriate grid size that depends on the problem. Finally, we demonstrate the computational feasibility of our algorithm for multiple-order derivative regularization operators.
-
solving Continuous Domain problems exactly with multiresolution b splines
International Conference on Acoustics Speech and Signal Processing, 2019Co-Authors: Thomas Debarre, Harshit Gupta, Julien Fageot, Michael UnserAbstract:We propose a discretization method for Continuous-Domain linear inverse problems with multiple-order total-variation (TV) regularization. It is based on a recent result that proves that such inverse problems have sparse polynomial-spline solutions. Our method consists in restricting the search space to splines with knots on a uniform grid, which results in a standard convex finite-dimensional problem. As basis functions for this search space, we use the B-splines matched to the regularization order, which are optimally localized. This leads to a well-conditioned, computationally feasible optimization task. Our proposed iterative multiresolution algorithm then refines the grid size until a desired level of accuracy is met and converges to sparse solutions of our inverse problem. Finally, we present experimental results that validate our approach.
-
B-Spline-Based Exact Discretization of Continuous-Domain Inverse Problems With Generalized TV Regularization
IEEE Transactions on Information Theory, 2019Co-Authors: Thomas Debarre, Harshit Gupta, Julien Fageot, Michael UnserAbstract:We study Continuous-Domain linear inverse problems with generalized total-variation (gTV) regularization, expressed in terms of a regularization operator L. It has recently been proved that such inverse problems have sparse spline solutions, with fewer jumps than the number of measurements. Moreover, the type of spline solely depends on L (L-splines) and is independent of the measurements. The Continuous-Domain inverse problem can be recast in an exact way as a finite-dimensional problem by restricting the search space to splines with knots on a uniform finite grid. However, expressing the L-spline coefficients in the dictionary basis of the Green’s function of L is ill-suited for practical problems due to its infinite support. Instead, we propose to formulate the problem in the B-spline dictionary basis, which leads to better-conditioned problems. As we make the grid finer, we show that a solution of the Continuous-Domain problem can be approached arbitrarily closely with functions of this search space. This result motivates our proposed multiresolution algorithm, which computes sparse solutions of our inverse problem. We demonstrate that this algorithm is computationally feasible for 1D signals when L is an ordinary differential operator.
-
Continuous Domain solutions of linear inverse problems with tikhonov versus generalized tv regularization
IEEE Transactions on Signal Processing, 2018Co-Authors: Harshit Gupta, Julien Fageot, Michael UnserAbstract:We consider one-dimensional (1-D) linear inverse problems that are formulated in the Continuous Domain. The object of recovery is a function that is assumed to minimize a convex objective functional. The solutions are constrained by imposing a Continuous-Domain regularization. We derive the parametric form of the solution (representer theorems) for Tikhonov (quadratic) and generalized total-variation (gTV) regularizations. We show that, in both cases, the solutions are splines that are intimately related to the regularization operator. In the Tikhonov case, the solution is smooth and constrained to live in a fixed subspace that depends on the measurement operator. By contrast, the gTV regularization results in a sparse solution composed of only a few dictionary elements that are upper-bounded by the number of measurements and independent of the measurement operator. Our findings for the gTV regularization resonates with the minimization of the $\ell _1$ norm, which is its discrete counterpart and also produces sparse solutions. Finally, we find the experimental solutions for some measurement models in one dimension. We discuss the special case when the gTV regularization results in multiple solutions and devise an algorithm to find an extreme point of the solution set which is guaranteed to be sparse.
Tobias Glasmachers - One of the best experts on this subject based on the ideXlab platform.
-
drift theory in Continuous search spaces expected hitting time of the 1 1 es with 1 5 success rule
Genetic and Evolutionary Computation Conference, 2018Co-Authors: Youhei Akimoto, Anne Auger, Tobias GlasmachersAbstract:This paper explores the use of the standard approach for proving runtime bounds in discrete Domains---often referred to as drift analysis---in the context of optimization on a Continuous Domain. Using this framework we analyze the (1+1) Evolution Strategy with one-fifth success rule on the sphere function. To deal with potential functions that are not lower-bounded, we formulate novel drift theorems. We then use the theorems to prove bounds on the expected hitting time to reach a certain target fitness in finite dimension d. The bounds are akin to linear convergence. We then study the dependency of the different terms on d proving a convergence rate dependency of Θ(1/d). Our results constitute the first non-asymptotic analysis for the algorithm considered as well as the first explicit application of drift analysis to a randomized search heuristic with Continuous Domain.
-
GECCO - Drift theory in Continuous search spaces: expected hitting time of the (1 + 1)-ES with 1/5 success rule
Proceedings of the Genetic and Evolutionary Computation Conference, 2018Co-Authors: Youhei Akimoto, Anne Auger, Tobias GlasmachersAbstract:This paper explores the use of the standard approach for proving runtime bounds in discrete Domains---often referred to as drift analysis---in the context of optimization on a Continuous Domain. Using this framework we analyze the (1+1) Evolution Strategy with one-fifth success rule on the sphere function. To deal with potential functions that are not lower-bounded, we formulate novel drift theorems. We then use the theorems to prove bounds on the expected hitting time to reach a certain target fitness in finite dimension d. The bounds are akin to linear convergence. We then study the dependency of the different terms on d proving a convergence rate dependency of Θ(1/d). Our results constitute the first non-asymptotic analysis for the algorithm considered as well as the first explicit application of drift analysis to a randomized search heuristic with Continuous Domain.
-
Drift Theory in Continuous Search Spaces: Expected Hitting Time of the (1+1)-ES with 1/5 Success Rule
arXiv: Neural and Evolutionary Computing, 2018Co-Authors: Youhei Akimoto, Anne Auger, Tobias GlasmachersAbstract:This paper explores the use of the standard approach for proving runtime bounds in discrete Domains---often referred to as drift analysis---in the context of optimization on a Continuous Domain. Using this framework we analyze the (1+1) Evolution Strategy with one-fifth success rule on the sphere function. To deal with potential functions that are not lower-bounded, we formulate novel drift theorems. We then use the theorems to prove bounds on the expected hitting time to reach a certain target fitness in finite dimension $d$. The bounds are akin to linear convergence. We then study the dependency of the different terms on $d$ proving a convergence rate dependency of $\Theta(1/d)$. Our results constitute the first non-asymptotic analysis for the algorithm considered as well as the first explicit application of drift analysis to a randomized search heuristic with Continuous Domain.
Youhei Akimoto - One of the best experts on this subject based on the ideXlab platform.
-
generalized drift analysis in Continuous Domain linear convergence of 1 1 es on strongly convex functions with lipschitz Continuous gradients
Foundations of Genetic Algorithms, 2019Co-Authors: Daiki Morinaga, Youhei AkimotoAbstract:We prove the linear convergence of the (1 + 1)-Evolution Strategy (ES) with a success based step-size adaptation on a broad class of functions, including strongly convex functions with Lipschitz Continuous gradients, which is often assumed to analyze gradient based methods. Our proof is based on the methodology recently developed to analyze the same algorithm on the spherical function, namely the additive drift analysis on unbounded Continuous Domain. An upper bound of the expected first hitting time is derived, from which we can conclude that our algorithm converges linearly. We investigate the class of functions that satisfy the assumptions of our main theorem, revealing that strongly convex functions with Lipschitz Continuous gradients and their strictly increasing transformation satisfy the assumptions. To the best of our knowledge, this is the first paper showing the linear convergence of the (1+1)-ES on such a broad class of functions. This opens the possibility to compare the (1 + 1)-ES and gradient based methods in theory.
-
GECCO - Drift theory in Continuous search spaces: expected hitting time of the (1 + 1)-ES with 1/5 success rule
Proceedings of the Genetic and Evolutionary Computation Conference, 2018Co-Authors: Youhei Akimoto, Anne Auger, Tobias GlasmachersAbstract:This paper explores the use of the standard approach for proving runtime bounds in discrete Domains---often referred to as drift analysis---in the context of optimization on a Continuous Domain. Using this framework we analyze the (1+1) Evolution Strategy with one-fifth success rule on the sphere function. To deal with potential functions that are not lower-bounded, we formulate novel drift theorems. We then use the theorems to prove bounds on the expected hitting time to reach a certain target fitness in finite dimension d. The bounds are akin to linear convergence. We then study the dependency of the different terms on d proving a convergence rate dependency of Θ(1/d). Our results constitute the first non-asymptotic analysis for the algorithm considered as well as the first explicit application of drift analysis to a randomized search heuristic with Continuous Domain.
-
drift theory in Continuous search spaces expected hitting time of the 1 1 es with 1 5 success rule
Genetic and Evolutionary Computation Conference, 2018Co-Authors: Youhei Akimoto, Anne Auger, Tobias GlasmachersAbstract:This paper explores the use of the standard approach for proving runtime bounds in discrete Domains---often referred to as drift analysis---in the context of optimization on a Continuous Domain. Using this framework we analyze the (1+1) Evolution Strategy with one-fifth success rule on the sphere function. To deal with potential functions that are not lower-bounded, we formulate novel drift theorems. We then use the theorems to prove bounds on the expected hitting time to reach a certain target fitness in finite dimension d. The bounds are akin to linear convergence. We then study the dependency of the different terms on d proving a convergence rate dependency of Θ(1/d). Our results constitute the first non-asymptotic analysis for the algorithm considered as well as the first explicit application of drift analysis to a randomized search heuristic with Continuous Domain.
-
Drift Theory in Continuous Search Spaces: Expected Hitting Time of the (1+1)-ES with 1/5 Success Rule
arXiv: Neural and Evolutionary Computing, 2018Co-Authors: Youhei Akimoto, Anne Auger, Tobias GlasmachersAbstract:This paper explores the use of the standard approach for proving runtime bounds in discrete Domains---often referred to as drift analysis---in the context of optimization on a Continuous Domain. Using this framework we analyze the (1+1) Evolution Strategy with one-fifth success rule on the sphere function. To deal with potential functions that are not lower-bounded, we formulate novel drift theorems. We then use the theorems to prove bounds on the expected hitting time to reach a certain target fitness in finite dimension $d$. The bounds are akin to linear convergence. We then study the dependency of the different terms on $d$ proving a convergence rate dependency of $\Theta(1/d)$. Our results constitute the first non-asymptotic analysis for the algorithm considered as well as the first explicit application of drift analysis to a randomized search heuristic with Continuous Domain.
Martin Mauve - One of the best experts on this subject based on the ideXlab platform.
-
CSCW - Consistency in replicated Continuous interactive media
Proceedings of the 2000 ACM conference on Computer supported cooperative work - CSCW '00, 2000Co-Authors: Martin MauveAbstract:In this paper we investigate how consistency can be ensured for replicated Continuous interactive media, i.e., replicated media which change their state in reaction to user initiated operations as well as because of the passing of time. Typical examples for this media class are networked computer games and distributed VR applications. Existing approaches to reach consistency for replicated discrete interactive media are briefly outlined and it is shown that these fail in the Continuous Domain. In order to allow a thorough discussion of the problem, a formal definition of the term consistency in the Continuous Domain is given. Based on this definition we show that an important tradeoff relationship exists between the responsiveness of the medium and the appearance of short-term inconsistencies. Until now this tradeoff was not taken into consideration for consistency in the Continuous Domain, thereby severely limiting the consistency related fidelity for a large number of applications. We show that for those applications the fidelity can be significantly raised by voluntarily decreasing the responsiveness of the medium. This concept is called local lag. It enables the distribution of Continuous interactive media that are more vulnerable to short-term inconsistencies than, e.g., battlefield simulations. We prove that the concept of local lag is valid by describing how local lag was successfully used to ensure consistency in a 3D telecooperation application.
-
consistency in replicated Continuous interactive media
Conference on Computer Supported Cooperative Work, 2000Co-Authors: Martin MauveAbstract:In this paper we investigate how consistency can be ensured for replicated Continuous interactive media, i.e., replicated media which change their state in reaction to user initiated operations as well as because of the passing of time. Typical examples for this media class are networked computer games and distributed VR applications. Existing approaches to reach consistency for replicated discrete interactive media are briefly outlined and it is shown that these fail in the Continuous Domain. In order to allow a thorough discussion of the problem, a formal definition of the term consistency in the Continuous Domain is given. Based on this definition we show that an important tradeoff relationship exists between the responsiveness of the medium and the appearance of short-term inconsistencies. Until now this tradeoff was not taken into consideration for consistency in the Continuous Domain, thereby severely limiting the consistency related fidelity for a large number of applications. We show that for those applications the fidelity can be significantly raised by voluntarily decreasing the responsiveness of the medium. This concept is called local lag. It enables the distribution of Continuous interactive media that are more vulnerable to short-term inconsistencies than, e.g., battlefield simulations. We prove that the concept of local lag is valid by describing how local lag was successfully used to ensure consistency in a 3D telecooperation application.
-
Consistency in Continuous Distributed Interactive Media
1999Co-Authors: Martin MauveAbstract:In this paper we investigate how consistency can be ensured for Continuous distributed interactive media, i.e. distributed media which change their state in reaction to user initiated operations as well as because of the passing of time. Existing approaches to reach consistency in discrete distributed interactive media are briefly outlined and it is shown that these fail in the Continuous Domain. In order to allow a thorough discussion of the problem, a formal definition of the term consistency in the Continuous Domain is given. Based on this definition we show that an important trade off relationship exists between the responsiveness of the medium and the appearance of short term inconsistencies. Currently this trade off is not taken into consideration for consistency in the Continuous Domain, thereby severely limiting the consistency related fidelity for a large number of applications. We show that for those applications the fidelity can be significantly raised by voluntarily decreasing the responsiveness of the medium. This concept is called local lag and it enables the distribution of Continuous interactive media which are more vulnerable to short term inconsistencies than e.g. battlefield simulations. We prove that the concept of local lag is valid by describing how local lag was successfully used to ensure consistency in a 3D telecooperation application.
Qiyu Sun - One of the best experts on this subject based on the ideXlab platform.
-
a unified formulation of gaussian versus sparse stochastic processes part i Continuous Domain theory
IEEE Transactions on Information Theory, 2014Co-Authors: Michael Unser, Pouya Dehghani Tafti, Qiyu SunAbstract:We introduce a general distributional framework that results in a unifying description and characterization of a rich variety of Continuous-time stochastic processes. The cornerstone of our approach is an innovation model that is driven by some generalized white noise process, which may be Gaussian or not (e.g., Laplace, impulsive Poisson, or alpha stable). This allows for a conceptual decoupling between the correlation properties of the process, which are imposed by the whitening operator L, and its sparsity pattern, which is determined by the type of noise excitation. The latter is fully specified by a Levy measure. We show that the range of admissible innovation behavior varies between the purely Gaussian and super-sparse extremes. We prove that the corresponding generalized stochastic processes are well-defined mathematically provided that the (adjoint) inverse of the whitening operator satisfies some Lp bound for p ≥ 1. We present a novel operator-based method that yields an explicit characterization of all Levy-driven processes that are solutions of constant-coefficient stochastic differential equations. When the underlying system is stable, we recover the family of stationary Continuous-time autoregressive moving average processes (CARMA), including the Gaussian ones. The approach remains valid when the system is unstable and leads to the identification of potentially useful generalizations of the Levy processes, which are sparse and non-stationary. Finally, we show that these processes admit a sparse representation in some matched wavelet Domain and provide a full characterization of their transform-Domain statistics.
-
a unified formulation of gaussian vs sparse stochastic processes part i Continuous Domain theory
arXiv: Information Theory, 2011Co-Authors: Michael Unser, Pouya Dehghani Tafti, Qiyu SunAbstract:We introduce a general distributional framework that results in a unifying description and characterization of a rich variety of Continuous-time stochastic processes. The cornerstone of our approach is an innovation model that is driven by some generalized white noise process, which may be Gaussian or not (e.g., Laplace, impulsive Poisson or alpha stable). This allows for a conceptual decoupling between the correlation properties of the process, which are imposed by the whitening operator L, and its sparsity pattern which is determined by the type of noise excitation. The latter is fully specified by a Levy measure. We show that the range of admissible innovation behavior varies between the purely Gaussian and super-sparse extremes. We prove that the corresponding generalized stochastic processes are well-defined mathematically provided that the (adjoint) inverse of the whitening operator satisfies some Lp bound for p>=1. We present a novel operator-based method that yields an explicit characterization of all Levy-driven processes that are solutions of constant-coefficient stochastic differential equations. When the underlying system is stable, we recover the family of stationary CARMA processes, including the Gaussian ones. The approach remains valid when the system is unstable and leads to the identification of potentially useful generalizations of the Levy processes, which are sparse and non-stationary. Finally, we show how we can apply finite difference operators to obtain a stationary characterization of these processes that is maximally decoupled and stable, irrespective of the location of the poles in the complex plane.