The Experts below are selected from a list of 12003 Experts worldwide ranked by ideXlab platform
Babak Hassibi - One of the best experts on this subject based on the ideXlab platform.
-
Sharp MSE Bounds for Proximal Denoising
Foundations of Computational Mathematics, 2016Co-Authors: Samet Oymak, Babak HassibiAbstract:Denoising has to do with estimating a signal $$\mathbf {x}_0$$ x 0 from its noisy observations $$\mathbf {y}=\mathbf {x}_0+\mathbf {z}$$ y = x 0 + z . In this paper, we focus on the “structured Denoising Problem,” where the signal $$\mathbf {x}_0$$ x 0 possesses a certain structure and $$\mathbf {z}$$ z has independent normally distributed entries with mean zero and variance $$\sigma ^2$$ σ 2 . We employ a structure-inducing convex function $$f(\cdot )$$ f ( · ) and solve $$\min _\mathbf {x}\{\frac{1}{2}\Vert \mathbf {y}-\mathbf {x}\Vert _2^2+\sigma {\lambda }f(\mathbf {x})\}$$ min x { 1 2 ‖ y - x ‖ 2 2 + σ λ f ( x ) } to estimate $$\mathbf {x}_0$$ x 0 , for some $$\lambda >0$$ λ > 0 . Common choices for $$f(\cdot )$$ f ( · ) include the $$\ell _1$$ ℓ 1 norm for sparse vectors, the $$\ell _1-\ell _2$$ ℓ 1 - ℓ 2 norm for block-sparse signals and the nuclear norm for low-rank matrices. The metric we use to evaluate the performance of an estimate $$\mathbf {x}^*$$ x ∗ is the normalized mean-squared error $$\text {NMSE}(\sigma )=\frac{{\mathbb {E}}\Vert \mathbf {x}^*-\mathbf {x}_0\Vert _2^2}{\sigma ^2}$$ NMSE ( σ ) = E ‖ x ∗ - x 0 ‖ 2 2 σ 2 . We show that NMSE is maximized as $$\sigma \rightarrow 0$$ σ → 0 and we find the exact worst-case NMSE, which has a simple geometric interpretation: the mean-squared distance of a standard normal vector to the $${\lambda }$$ λ -scaled subdifferential $${\lambda }\partial f(\mathbf {x}_0)$$ λ ∂ f ( x 0 ) . When $${\lambda }$$ λ is optimally tuned to minimize the worst-case NMSE, our results can be related to the constrained Denoising Problem $$\min _{f(\mathbf {x})\le f(\mathbf {x}_0)}\{\Vert \mathbf {y}-\mathbf {x}\Vert _2\}$$ min f ( x ) ≤ f ( x 0 ) { ‖ y - x ‖ 2 } . The paper also connects these results to the generalized LASSO Problem, in which one solves $$\min _{f(\mathbf {x})\le f(\mathbf {x}_0)}\{\Vert \mathbf {y}-{\mathbf {A}}\mathbf {x}\Vert _2\}$$ min f ( x ) ≤ f ( x 0 ) { ‖ y - A x ‖ 2 } to estimate $$\mathbf {x}_0$$ x 0 from noisy linear observations $$\mathbf {y}={\mathbf {A}}\mathbf {x}_0+\mathbf {z}$$ y = A x 0 + z . We show that certain properties of the LASSO Problem are closely related to the Denoising Problem. In particular, we characterize the normalized LASSO cost and show that it exhibits a “phase transition” as a function of number of observations. We also provide an order-optimal bound for the LASSO error in terms of the mean-squared distance. Our results are significant in two ways. First, we find a simple formula for the performance of a general convex estimator. Secondly, we establish a connection between the Denoising and linear inverse Problems.
-
Sharp MSE Bounds for Proximal Denoising
arXiv: Information Theory, 2013Co-Authors: Samet Oymak, Babak HassibiAbstract:Denoising has to do with estimating a signal $x_0$ from its noisy observations $y=x_0+z$. In this paper, we focus on the "structured Denoising Problem", where the signal $x_0$ possesses a certain structure and $z$ has independent normally distributed entries with mean zero and variance $\sigma^2$. We employ a structure-inducing convex function $f(\cdot)$ and solve $\min_x\{\frac{1}{2}\|y-x\|_2^2+\sigma\lambda f(x)\}$ to estimate $x_0$, for some $\lambda>0$. Common choices for $f(\cdot)$ include the $\ell_1$ norm for sparse vectors, the $\ell_1-\ell_2$ norm for block-sparse signals and the nuclear norm for low-rank matrices. The metric we use to evaluate the performance of an estimate $x^*$ is the normalized mean-squared-error $\text{NMSE}(\sigma)=\frac{\mathbb{E}\|x^*-x_0\|_2^2}{\sigma^2}$. We show that NMSE is maximized as $\sigma\rightarrow 0$ and we find the \emph{exact} worst case NMSE, which has a simple geometric interpretation: the mean-squared-distance of a standard normal vector to the $\lambda$-scaled subdifferential $\lambda\partial f(x_0)$. When $\lambda$ is optimally tuned to minimize the worst-case NMSE, our results can be related to the constrained Denoising Problem $\min_{f(x)\leq f(x_0)}\{\|y-x\|_2\}$. The paper also connects these results to the generalized LASSO Problem, in which, one solves $\min_{f(x)\leq f(x_0)}\{\|y-Ax\|_2\}$ to estimate $x_0$ from noisy linear observations $y=Ax_0+z$. We show that certain properties of the LASSO Problem are closely related to the Denoising Problem. In particular, we characterize the normalized LASSO cost and show that it exhibits a "phase transition" as a function of number of observations. Our results are significant in two ways. First, we find a simple formula for the performance of a general convex estimator. Secondly, we establish a connection between the Denoising and linear inverse Problems.
-
Allerton Conference - On a relation between the minimax risk and the phase transitions of compressed recovery
2012 50th Annual Allerton Conference on Communication Control and Computing (Allerton), 2012Co-Authors: Samet Oymak, Babak HassibiAbstract:This paper provides a sharp analysis of the optimally tuned Denoising Problem and establishes a relation between the estimation error (minimax risk) and phase transition for compressed sensing recovery using convex and continuous functions. Phase transitions deal with recovering a signal xo from compressed linear observations Ax 0 by minimizing a certain convex function f(·). On the other hand, Denoising is the Problem of estimating a signal x 0 from noisy observations y = x 0 +z using the regularization min x λ/f(x) + ½‖y−x‖ 2 2. In general, these Problems are more meaningful and useful when the signal x 0 has a certain structure and the function f(·) is chosen to exploit this structure. Examples include, l 1 and l 1 − l 2 norms for sparse and block sparse vectors and nuclear norm for low rank matrices. In this work, we carefully analyze the minimax Denoising Problem and relate our results to the phase transition performance under a considerably general setting where the measurement A in compressed recovery and the noise z in the Denoising Problem are iid Gaussian random variables. Our results suggest that the required number of observations to recover a compressed signal is closely related to the asymptotic variance of the optimal estimation error. This relation was first empirically noted in [9]. Here we provide a rigorous foundation.
Matteo Novaga - One of the best experts on this subject based on the ideXlab platform.
-
TV Denoising of two balls in the plane
arXiv: Functional Analysis, 2016Co-Authors: Vicent Caselles, Matteo Novaga, Christiane PöschlAbstract:The aim of this paper is to compute the explicit solution of the total variation Denoising Problem corresponding to the characteristic function of a set which is the union of two planar disjoint balls with different radii.
-
regularity for solutions of the total variation Denoising Problem
Revista Matematica Iberoamericana, 2011Co-Authors: Vicent Caselles, Antonin Chambolle, Matteo NovagaAbstract:The main purpose of this paper is to prove a local Holder regularity result for the solutions of the total variation based Denoising Problem assuming that the datum is locally Holder continuous. We also prove a global estimate on the modulus of continuity of the solution in convex domains of R and some extensions of this result for the total variation minimization flow.
-
The Discontinuity Set of Solutions of the TV Denoising Problem and Some Extensions
Multiscale Modeling & Simulation, 2007Co-Authors: Vicent Caselles, Antonin Chambolle, Matteo NovagaAbstract:The main purpose of this paper is to prove that the jump discontinuity set of the solution of the total variation based Denoising Problem is contained in the jump set of the datum to be denoised. We also prove some extensions of this result for the total variation minimization flow, for anisotropic norms, and for some more general convex functionals, which include the minimal surface equation case and its anisotropic extensions
-
Explicit Solutions of the Eigenvalue Problem $div \left(\frac Du\vert Du \vert \right)=u$ in $R^2$
SIAM Journal on Mathematical Analysis, 2005Co-Authors: Giovanni Bellettini, Vicent Caselles, Matteo NovagaAbstract:In this paper we compute explicit solutions of the eigenvalue Problem $-div (Du /\vert D u\vert) = u$ in $R^2$, in particular explicit solutions whose truncatures are in $W^{1,1}_{{\rm loc}}(R^2)$, and piecewise constant ones which are sums of characteristic functions of convex sets. The solutions of the above eigenvalue Problem describe the asymptotic behavior of solutions of the minimizing total variation flow. As an application, we also construct explicit solutions of the Denoising Problem in image processing.
-
The Total Variation Flow
Free Boundary Problems, 2003Co-Authors: Matteo NovagaAbstract:We consider the gradient flow of the total variation functional, stating general existence and uniqueness results. Particular attention is paid to self-similar solutions, which are partially classified. Finally, as an application, some explicit solutions of the Denoising Problem are given.
Alex Sawatzky - One of the best experts on this subject based on the ideXlab platform.
-
performance of first order algorithms for tv penalized weighted least squares Denoising Problem
International Conference on Image and Signal Processing, 2014Co-Authors: Alex SawatzkyAbstract:Denoising of images perturbed by non-standard noise models (e.g., Poisson or Gamma noise) can be often realized by a sequence of penalized weighted least-squares minimization Problems. In the recent past, a variety of first-order algorithms have been proposed for convex Problems but their efficiency is usually tested with the classical least-squares data fidelity term. Thus, in this manuscript, first-order state-of-the-art computational schemes are applied on a total variation penalized weighted least-squares Denoising Problem and their performance is evaluated on numerical examples simulating a Poisson noise perturbation.
-
ICISP - Performance of First-Order Algorithms for TV Penalized Weighted Least-Squares Denoising Problem
Lecture Notes in Computer Science, 2014Co-Authors: Alex SawatzkyAbstract:Denoising of images perturbed by non-standard noise models (e.g., Poisson or Gamma noise) can be often realized by a sequence of penalized weighted least-squares minimization Problems. In the recent past, a variety of first-order algorithms have been proposed for convex Problems but their efficiency is usually tested with the classical least-squares data fidelity term. Thus, in this manuscript, first-order state-of-the-art computational schemes are applied on a total variation penalized weighted least-squares Denoising Problem and their performance is evaluated on numerical examples simulating a Poisson noise perturbation.
Antonin Chambolle - One of the best experts on this subject based on the ideXlab platform.
-
Error estimates for finite differences approximations of the total variation
2020Co-Authors: Corentin Caillaud, Antonin ChambolleAbstract:We present a convergence rate analysis of the Rudin-Osher-Fatemi (ROF) Denoising Problem for two different discretizations of the total variation. The first discretization is the well-known isotropic total variation that suffers from a blurring effect in a special diagonal direction. We prove that in the setting corresponding to this direction, the discrete ROF energy converges to the continuous one in O(h^2/3). The second total variation is based on Raviart-Thomas fields and achieves a O(h) convergence rate for the same quantity under some standard hypotheses.
-
geometric properties of solutions to the total variation Denoising Problem
Inverse Problems, 2017Co-Authors: Antonin Chambolle, Vincent Duval, Gabriel Peyre, Clarice PoonAbstract:This article studies the Denoising performance of total variation (TV) image regularization. More precisely, we study geometrical properties of the solution to the so-called Rudin-Osher-Fatemi total variation Denoising method. The first contribution of this paper is a precise mathematical definition of the “extended support” (associated to the noise-free image) of TV Denoising. It is intuitively the region which is unstable and will suffer from the staircasing effect. We highlight in several practical cases, such as the indicator of convex sets, that this region can be determined explicitly. Our second and main contribution is a proof that the TV Denoising method indeed restores an image which is exactly constant outside a small tube surrounding the extended support. The radius of this tube shrinks toward zero as the noise level vanishes, and are able to determine, in some cases, an upper bound on the convergence rate. For indicators of so-called “calibrable” sets (such as disks or properly eroded squares), this extended support matches the edges, so that discontinuities produced by TV Denoising cluster tightly around the edges. In contrast, for indicators of more general shapes or for complicated images, this extended support can be larger. Beside these main results, our paper also proves several intermediate results about fine properties of TV regularization, in particular for indicators of calibrable and convex sets, which are of independent interest.
-
regularity for solutions of the total variation Denoising Problem
Revista Matematica Iberoamericana, 2011Co-Authors: Vicent Caselles, Antonin Chambolle, Matteo NovagaAbstract:The main purpose of this paper is to prove a local Holder regularity result for the solutions of the total variation based Denoising Problem assuming that the datum is locally Holder continuous. We also prove a global estimate on the modulus of continuity of the solution in convex domains of R and some extensions of this result for the total variation minimization flow.
-
The Discontinuity Set of Solutions of the TV Denoising Problem and Some Extensions
Multiscale Modeling & Simulation, 2007Co-Authors: Vicent Caselles, Antonin Chambolle, Matteo NovagaAbstract:The main purpose of this paper is to prove that the jump discontinuity set of the solution of the total variation based Denoising Problem is contained in the jump set of the datum to be denoised. We also prove some extensions of this result for the total variation minimization flow, for anisotropic norms, and for some more general convex functionals, which include the minimal surface equation case and its anisotropic extensions
-
Evolution of characteristic functions of convex sets in the plane by the minimizing total variation flow
Interfaces and Free Boundaries, 2005Co-Authors: François Alter, Vicent Caselles, Antonin ChambolleAbstract:In this paper we compute the explicit evolution of the Minimizing Total Variation flow when the initial condition is the characteristic function of a convex set in R2, or a finite number of them which are sufficiently separated. We shall also obtain some explicit solutions of the Total Variation formulation of the Denoising Problem in image processing. We illustrate these results with some experiments.
Yu-fei Yang - One of the best experts on this subject based on the ideXlab platform.
-
A projection method based on the splitting Bregman iteration for the image Denoising
Journal of Applied Mathematics and Computing, 2011Co-Authors: Baoli Shi, Zhi-feng Pang, Yu-fei YangAbstract:By analyzing the connection between the projection operator and the shrink operator, we propose a projection method based on the splitting Bregman iteration for image Denoising Problem in this paper. Compared with the splitting Bregman method, the proposed method has a more compact form so that it is more fast and efficient. Following from the operator theory, the convergence of the proposed method is proved. Some numerical comparisons between the proposed method and the splitting Bregman method are arranged for solving two basic image Denoising models.