The Experts below are selected from a list of 6645 Experts worldwide ranked by ideXlab platform
John Wright - One of the best experts on this subject based on the ideXlab platform.
-
on the global geometry of sphere constrained sparse Blind Deconvolution
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021Co-Authors: Yuqian Zhang, Han-wen Kuo, Abhay Pasupathy, Yenson Lau, Sky C Cheung, John WrightAbstract:Blind Deconvolution is the problem of recovering a convolutional kernel $\boldsymbol{a}_0$ a 0 and an activation signal $\boldsymbol{x}_0$ x 0 from their convolution $\boldsymbol{y} = \boldsymbol{a}_0 \circledast \boldsymbol{x}_0$ y = a 0 ⊛ x 0 . This problem is ill-posed without further constraints or priors. This paper studies the situation where the nonzero entries in the activation signal are sparsely and randomly populated. We normalize the convolution kernel to have unit Frobenius norm and cast the sparse Blind Deconvolution problem as a nonconvex optimization problem over the sphere. With this spherical constraint, every spurious local minimum turns out to be close to some signed shift truncation of the ground truth, under certain hypotheses. This benign property motivates an effective two stage algorithm that recovers the ground truth from the partial information offered by a suboptimal local minimum. This geometry-inspired algorithm recovers the ground truth for certain microscopy problems, also exhibits promising performance in the more challenging image deblurring problem. Our insights into the global geometry and the two stage algorithm extend to the convolutional dictionary learning problem, where a superposition of multiple convolution signals is observed.
-
structured local optima in sparse Blind Deconvolution
IEEE Transactions on Information Theory, 2020Co-Authors: Yuqian Zhang, Han-wen Kuo, John WrightAbstract:Blind Deconvolution is a ubiquitous problem aiming to recover a convolution kernel $\boldsymbol a_{0}\in \mathbb R ^{k}$ and an activation signal $\boldsymbol x_{0}\in \mathbb R ^{m}$ from their convolution $\boldsymbol y\in \mathbb R ^{m}$ . Unfortunately, this is an ill-posed problem in general. This paper focuses on the short and sparse Blind Deconvolution problem, where the convolution kernel is short ( $k\ll m$ ) and the activation signal is sparsely and randomly supported ( $\left \|{ \boldsymbol x_{0} }\right \|_{0}\ll m$ ). This variant captures the structure of the convolutional signals in several important application scenarios. In this paper, we normalize the convolution kernel to have unit Frobenius norm and then cast the Blind Deconvolution problem as a nonconvex optimization problem over the kernel sphere. We demonstrate that (i) in a certain region of the sphere, every local optimum is close to some shift truncation of the ground truth, and (ii) for a generic unit kernel $\boldsymbol a_{0}$ , when the sparsity of activation signal satisfies $\theta \lesssim k^{-2/3}$ and number of measurements $m\gtrsim \mathop {\mathrm {poly}}\nolimits \left ({k }\right) $ , the proposed initialization method together with a descent algorithm which escapes strict saddle points recovers some shift truncation of the ground truth kernel.
-
Structured Local Optima in Sparse Blind Deconvolution
arXiv: Signal Processing, 2018Co-Authors: Yuqian Zhang, Han-wen Kuo, John Wright, John WrightAbstract:Blind Deconvolution is a ubiquitous problem of recovering two unknown signals from their convolution. Unfortunately, this is an ill-posed problem in general. This paper focuses on the {\em short and sparse} Blind Deconvolution problem, where the one unknown signal is short and the other one is sparsely and randomly supported. This variant captures the structure of the unknown signals in several important applications. We assume the short signal to have unit $\ell^2$ norm and cast the Blind Deconvolution problem as a nonconvex optimization problem over the sphere. We demonstrate that (i) in a certain region of the sphere, every local optimum is close to some shift truncation of the ground truth, and (ii) for a generic short signal of length $k$, when the sparsity of activation signal $\theta\lesssim k^{-2/3}$ and number of measurements $m\gtrsim poly(k)$, a simple initialization method together with a descent algorithm which escapes strict saddle points recovers a near shift truncation of the ground truth kernel.
-
On the Global Geometry of Sphere-Constrained Sparse Blind Deconvolution
2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017Co-Authors: Yuqian Zhang, Sky Cheung, Abhay Pasupathy, John WrightAbstract:Blind Deconvolution is the problem of recovering a convolutional kernel and an activation signal from their convolution y = a0 * x0. This problem is ill-posed without further constraints or priors. This paper studies the situation where the nonzero entries in the activation signal are sparsely and randomly populated. We normalize the convolution kernel to have unit Frobenius norm and cast the sparse Blind Deconvolution problem as a nonconvex optimization problem over the sphere. With this spherical constraint, every spurious local minimum turns out to be close to some signed shift truncation of the ground truth, under certain hypotheses. This benign property motivates an effective two stage algorithm that recovers the ground truth from the partial information offered by a suboptimal local minimum. This geometry-inspired algorithm recovers the ground truth for certain microscopy problems, also exhibits promising performance in the more challenging image deblurring problem. Our insights into the global geometry and the two stage algorithm extend to the convolutional dictionary learning problem, where a superposition of multiple convolution signals is observed.
Yuqian Zhang - One of the best experts on this subject based on the ideXlab platform.
-
on the global geometry of sphere constrained sparse Blind Deconvolution
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021Co-Authors: Yuqian Zhang, Han-wen Kuo, Abhay Pasupathy, Yenson Lau, Sky C Cheung, John WrightAbstract:Blind Deconvolution is the problem of recovering a convolutional kernel $\boldsymbol{a}_0$ a 0 and an activation signal $\boldsymbol{x}_0$ x 0 from their convolution $\boldsymbol{y} = \boldsymbol{a}_0 \circledast \boldsymbol{x}_0$ y = a 0 ⊛ x 0 . This problem is ill-posed without further constraints or priors. This paper studies the situation where the nonzero entries in the activation signal are sparsely and randomly populated. We normalize the convolution kernel to have unit Frobenius norm and cast the sparse Blind Deconvolution problem as a nonconvex optimization problem over the sphere. With this spherical constraint, every spurious local minimum turns out to be close to some signed shift truncation of the ground truth, under certain hypotheses. This benign property motivates an effective two stage algorithm that recovers the ground truth from the partial information offered by a suboptimal local minimum. This geometry-inspired algorithm recovers the ground truth for certain microscopy problems, also exhibits promising performance in the more challenging image deblurring problem. Our insights into the global geometry and the two stage algorithm extend to the convolutional dictionary learning problem, where a superposition of multiple convolution signals is observed.
-
structured local optima in sparse Blind Deconvolution
IEEE Transactions on Information Theory, 2020Co-Authors: Yuqian Zhang, Han-wen Kuo, John WrightAbstract:Blind Deconvolution is a ubiquitous problem aiming to recover a convolution kernel $\boldsymbol a_{0}\in \mathbb R ^{k}$ and an activation signal $\boldsymbol x_{0}\in \mathbb R ^{m}$ from their convolution $\boldsymbol y\in \mathbb R ^{m}$ . Unfortunately, this is an ill-posed problem in general. This paper focuses on the short and sparse Blind Deconvolution problem, where the convolution kernel is short ( $k\ll m$ ) and the activation signal is sparsely and randomly supported ( $\left \|{ \boldsymbol x_{0} }\right \|_{0}\ll m$ ). This variant captures the structure of the convolutional signals in several important application scenarios. In this paper, we normalize the convolution kernel to have unit Frobenius norm and then cast the Blind Deconvolution problem as a nonconvex optimization problem over the kernel sphere. We demonstrate that (i) in a certain region of the sphere, every local optimum is close to some shift truncation of the ground truth, and (ii) for a generic unit kernel $\boldsymbol a_{0}$ , when the sparsity of activation signal satisfies $\theta \lesssim k^{-2/3}$ and number of measurements $m\gtrsim \mathop {\mathrm {poly}}\nolimits \left ({k }\right) $ , the proposed initialization method together with a descent algorithm which escapes strict saddle points recovers some shift truncation of the ground truth kernel.
-
Structured Local Optima in Sparse Blind Deconvolution
arXiv: Signal Processing, 2018Co-Authors: Yuqian Zhang, Han-wen Kuo, John Wright, John WrightAbstract:Blind Deconvolution is a ubiquitous problem of recovering two unknown signals from their convolution. Unfortunately, this is an ill-posed problem in general. This paper focuses on the {\em short and sparse} Blind Deconvolution problem, where the one unknown signal is short and the other one is sparsely and randomly supported. This variant captures the structure of the unknown signals in several important applications. We assume the short signal to have unit $\ell^2$ norm and cast the Blind Deconvolution problem as a nonconvex optimization problem over the sphere. We demonstrate that (i) in a certain region of the sphere, every local optimum is close to some shift truncation of the ground truth, and (ii) for a generic short signal of length $k$, when the sparsity of activation signal $\theta\lesssim k^{-2/3}$ and number of measurements $m\gtrsim poly(k)$, a simple initialization method together with a descent algorithm which escapes strict saddle points recovers a near shift truncation of the ground truth kernel.
-
On the Global Geometry of Sphere-Constrained Sparse Blind Deconvolution
2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017Co-Authors: Yuqian Zhang, Sky Cheung, Abhay Pasupathy, John WrightAbstract:Blind Deconvolution is the problem of recovering a convolutional kernel and an activation signal from their convolution y = a0 * x0. This problem is ill-posed without further constraints or priors. This paper studies the situation where the nonzero entries in the activation signal are sparsely and randomly populated. We normalize the convolution kernel to have unit Frobenius norm and cast the sparse Blind Deconvolution problem as a nonconvex optimization problem over the sphere. With this spherical constraint, every spurious local minimum turns out to be close to some signed shift truncation of the ground truth, under certain hypotheses. This benign property motivates an effective two stage algorithm that recovers the ground truth from the partial information offered by a suboptimal local minimum. This geometry-inspired algorithm recovers the ground truth for certain microscopy problems, also exhibits promising performance in the more challenging image deblurring problem. Our insights into the global geometry and the two stage algorithm extend to the convolutional dictionary learning problem, where a superposition of multiple convolution signals is observed.
Paolo Favaro - One of the best experts on this subject based on the ideXlab platform.
-
Single Image Blind Deconvolution with Higher-Order Texture Statistics?
2016Co-Authors: Manuel Martinello, Paolo FavaroAbstract:Abstract. We present a novel method for solving Blind Deconvolution, i.e., the task of recovering a sharp image given a blurry one. We focus on blurry images obtained from a coded aperture camera, where both the camera and the scene are static, and allow blur to vary across the image domain. As most methods for Blind Deconvolution, we solve the prob-lem in two steps: First, we estimate the coded blur scale at each pixel; second, we deconvolve the blurry image given the estimated blur. Our approach is to use linear high-order priors for texture and second-order priors for the blur scale map, i.e., constraints involving two pixels at a time. We show that by incorporating the texture priors in a least-squares energy minimization we can transform the initial Blind Deconvolution task in a simpler optimization problem. One of the striking features of the simplified optimization problem is that the parameters that define the functional can be learned offline directly from natural images via sin-gular value decomposition. We also show a geometrical interpretation of image blurring and explain our method from this viewpoint. In doing so we devise a novel technique to design optimally coded apertures. Finally, our coded blur identification results in computing convolutions, rather than Deconvolutions, which are stable operations. We will demonstrate in several experiments that this additional stability allows the method to deal with large blur. We also compare our method to existing algorithms in the literature and show that we achieve state-of-the-art performance with both synthetic and real data
-
A Logarithmic Image Prior for Blind Deconvolution
International Journal of Computer Vision, 2016Co-Authors: Daniele Perrone, Paolo FavaroAbstract:Blind Deconvolution consists in the estimation of a sharp image and a blur kernel from an observed blurry image. Because the blur model admits several solutions it is necessary to devise an image prior that favors the true blur kernel and sharp image. Many successful image priors enforce the sparsity of the sharp image gradients. Ideally the $$L_0$$ L 0 “norm” is the best choice for promoting sparsity, but because it is computationally intractable, some methods have used a logarithmic approximation. In this work we also study a logarithmic image prior. We show empirically how well the prior suits the Blind Deconvolution problem. Our analysis confirms experimentally the hypothesis that a prior should not necessarily model natural image statistics to correctly estimate the blur kernel. Furthermore, we show that a simple Maximum a Posteriori formulation is enough to achieve state of the art results. To minimize such formulation we devise two iterative minimization algorithms that cope with the non-convexity of the logarithmic prior: one obtained via the primal-dual approach and one via majorization-minimization.
-
A Clearer Picture of Total Variation Blind Deconvolution
IEEE transactions on pattern analysis and machine intelligence, 2015Co-Authors: Daniele Perrone, Paolo FavaroAbstract:Blind Deconvolution is the problem of recovering a sharp image and a blur kernel from a noisy blurry image. Recently, there has been a significant effort on understanding the basic mechanisms to solve Blind Deconvolution. While this effort resulted in the deployment of effective algorithms, the theoretical findings generated contrasting views on why these approaches worked. On the one hand, one could observe experimentally that alternating energy minimization algorithms converge to the desired solution. On the other hand, it has been shown that such alternating minimization algorithms should fail to converge and one should instead use a so-called Variational Bayes approach. To clarify this conundrum, recent work showed that a good image and blur prior is instead what makes a Blind Deconvolution algorithm work. Unfortunately, this analysis did not apply to algorithms based on total variation regularization. In this manuscript, we provide both analysis and experiments to get a clearer picture of Blind Deconvolution. Our analysis reveals the very reason why an algorithm based on total variation works. We also introduce an implementation of this algorithm and show that, in spite of its extreme simplicity, it is very robust and achieves a performance comparable to the top performing algorithms.
-
Blind Deconvolution via lower bounded logarithmic image priors
Energy Minimization Methods in Computer Vision and Pattern Recognition, 2015Co-Authors: Daniele Perrone, Remo Diethelm, Paolo FavaroAbstract:In this work we devise two novel algorithms for Blind Deconvolution based on a family of logarithmic image priors. In contrast to recent approaches, we consider a minimalistic formulation of the Blind Deconvolution problem where there are only two energy terms: a least-squares term for the data fidelity and an image prior based on a lower-bounded logarithm of the norm of the image gradients. We show that this energy formulation is sufficient to achieve the state of the art in Blind Deconvolution with a good margin over previous methods. Much of the performance is due to the chosen prior. On the one hand, this prior is very effective in favoring sparsity of the image gradients. On the other hand, this prior is non convex. Therefore, solutions that can deal effectively with local minima of the energy become necessary. We devise two iterative minimization algorithms that at each iteration solve convex problems: one obtained via the primal-dual approach and one via majorization-minimization. While the former is computationally efficient, the latter achieves state-of-the-art performance on a public dataset.
Yonina C Eldar - One of the best experts on this subject based on the ideXlab platform.
-
unfolding neural networks for compressive multichannel Blind Deconvolution
arXiv: Signal Processing, 2020Co-Authors: Bahareh Tolooshams, Satish Mulleti, Yonina C EldarAbstract:We propose a learned-structured unfolding neural network for the problem of compressive sparse multichannel Blind-Deconvolution. In this problem, each channel's measurements are given as convolution of a common source signal and sparse filter. Unlike prior works where the compression is achieved either through random projections or by applying a fixed structured compression matrix, this paper proposes to learn the compression matrix from data. Given the full measurements, the proposed network is trained in an unsupervised fashion to learn the source and estimate sparse filters. Then, given the estimated source, we learn a structured compression operator while optimizing for signal reconstruction and sparse filter recovery. The efficient structure of the compression allows its practical hardware implementation. The proposed neural network is an autoencoder constructed based on an unfolding approach: upon training, the encoder maps the compressed measurements into an estimate of sparse filters using the compression operator and the source, and the linear convolutional decoder reconstructs the full measurements. We demonstrate that our method is superior to classical structured compressive sparse multichannel Blind-Deconvolution methods in terms of accuracy and speed of sparse filter recovery.
K. Tanebe - One of the best experts on this subject based on the ideXlab platform.
-
Super-exponential algorithms for multichannel Blind Deconvolution
IEEE Transactions on Signal Processing, 2000Co-Authors: Yujiro Inouye, K. TanebeAbstract:Multichannel Blind Deconvolution has been receiving increasing attention. Shalvi and Weinstein proposed an attractive approach to single-channel Blind Deconvolution called the super-exponential methods. The objective of this correspondence is to extend the Shalvi and Weinstein (1993, 1994) approach to the multichannel case and present super-exponential algorithms for multichannel Blind Deconvolution. We propose three approaches to multichannel Blind Deconvolution. In the first one, we present a multichannel super-exponential algorithm. In the second one, we present a super-exponential deflation algorithm. In the third one, we present a two-stage super-exponential algorithm.