In image restoration,we usually assume that the underlying image has a good sparse approximation under a certain system.Wavelet tight frame system has been proven to be such an efficient system to sparsely approximate...In image restoration,we usually assume that the underlying image has a good sparse approximation under a certain system.Wavelet tight frame system has been proven to be such an efficient system to sparsely approximate piecewise smooth images.Thus,it has been widely used in many practical image restoration problems.However,images from different scenarios are so diverse that no static wavelet tight frame system can sparsely approximate all of themwell.To overcome this,recently,Cai et.al.(Appl Comput Harmon Anal 37:89–105,2014)proposed a method that derives a data-driven tight frame adapted to the specific input image,leading to a better sparse approximation.The data-driven tight frame has been applied successfully to image denoising and CT image reconstruction.In this paper,we extend this data-driven tight frame construction method to multi-channel images.We construct a discrete tight frame system for each channel and assume their sparse coefficients have a joint sparsity.The multi-channel data-driven tight frame construction scheme is applied to joint color and depth image reconstruction.Experimental results show that the proposed approach has a better performance than state-of-the-art joint color and depth image reconstruction approaches.展开更多
Newton＇s iteration is modified for the computation of the group inverses of singular Toeplitz matrices. At each iteration, the iteration matrix is approximated by a matrix with a low displacement rank. Because of the...Newton＇s iteration is modified for the computation of the group inverses of singular Toeplitz matrices. At each iteration, the iteration matrix is approximated by a matrix with a low displacement rank. Because of the displacement structure of the iteration matrix, the matrix-vector multiplication involved in Newton＇s iteration can be done efficiently. We show that the convergence of the modified Newton iteration is still very fast. Numerical results are presented to demonstrate the fast convergence of the proposed method.展开更多
In this paper, two framelet based deconvolution algorithms are proposed. The basic idea of framelet based approach is to convert the deconvolution problem to the problem of inpainting in a frame domain by constructing...In this paper, two framelet based deconvolution algorithms are proposed. The basic idea of framelet based approach is to convert the deconvolution problem to the problem of inpainting in a frame domain by constructing a framelet system with one of the masks being the given （discrete） convolution kernel via the unitary extension principle of [26], as introduced in [6-9] . The first algorithm unifies our previous works in high resolution image reconstruction and infra-red chopped and nodded image restoration, and the second one is a combination of our previous frame-based deconvolution algorithm and the iterative thresholding algorithm given by [14, 16]. The strong convergence of the algorithms in infinite dimensional settings is given by employing proximal forward-backward splitting （PFBS） method. Consequently, it unifies iterative algorithms of infinite and finite dimensional setting and simplifies the proof of the convergence of the aluorithms of [6].展开更多
A fundamental problem in phase retrieval is to reconstruct an unknown signal from a set of magnitude-only measurements.In this work we introduce three novel quotient intensity models(QIMs) based on a deep modification...A fundamental problem in phase retrieval is to reconstruct an unknown signal from a set of magnitude-only measurements.In this work we introduce three novel quotient intensity models(QIMs) based on a deep modification of the traditional intensity-based models.A remarkable feature of the new loss functions is that the corresponding geometric landscape is benign under the optimal sampling complexity.When the measurements ai∈Rn are Gaussian random vectors and the number of measurements m≥Cn,the QIMs admit no spurious local minimizers with high probability,i.e.,the target solution x is the unique local minimizer(up to a global phase) and the loss function has a negative directional curvature around each saddle point.Such benign geometric landscape allows the gradient descent methods to find the global solution x(up to a global phase) without spectral initialization.展开更多
A fundamental task in phase retrieval is to recover an unknown signal x∈R^(n) from a set of magnitude-only measurements y_(i)=|〈a_(i),x〉|,i=1,…,m.In this paper,we propose two novel perturbed amplitude models(PAMs)...A fundamental task in phase retrieval is to recover an unknown signal x∈R^(n) from a set of magnitude-only measurements y_(i)=|〈a_(i),x〉|,i=1,…,m.In this paper,we propose two novel perturbed amplitude models(PAMs)which have a non-convex and quadratic-type loss function.When the measurements a_(i)∈R^(n) are Gaussian random vectors and the number of measurements m≥Cn,we rigorously prove that the PAMs admit no spurious local minimizers with high probability,i.e.,the target solution x is the unique local minimizer(up to a global phase)and the loss function has a negative directional curvature around each saddle point.Thanks to the well-tamed benign geometric landscape,one can employ the vanilla gradient descent method to locate the global minimizer x(up to a global phase)without spectral initialization.We carry out extensive numerical experiments to show that the gradient descent algorithm with random initialization outperforms state-of-the-art algorithms with spectral initialization in empirical success rate and convergence speed.展开更多
We investigate the problem of robust matrix completion with a fraction of observation corrupted by sparsity outlier noise.We propose an algorithmic framework based on the ADMM algorithm for a non-convex optimization,w...We investigate the problem of robust matrix completion with a fraction of observation corrupted by sparsity outlier noise.We propose an algorithmic framework based on the ADMM algorithm for a non-convex optimization,whose objective function consists of an l1 norm data fidelity and a rank constraint.To reduce the computational cost per iteration,two inexact schemes are developed to replace the most time-consuming step in the generic ADMM algorithm.The resulting algorithms remarkably outperform the existing solvers for robust matrix completion with outlier noise.When the noise is severe and the underlying matrix is ill-conditioned,the proposed algorithms are faster and give more accurate solutions than state-of-the-art robust matrix completion approaches.展开更多
Symmetric tensor decomposition is of great importance in applications.Several studies have employed a greedy approach,where the main idea is to first find a best rank-one approximation of a given tensor,and then repea...Symmetric tensor decomposition is of great importance in applications.Several studies have employed a greedy approach,where the main idea is to first find a best rank-one approximation of a given tensor,and then repeat the process to the residual tensor by subtracting the rank-one component.In this paper,we focus on finding a best rank-one approximation of a given orthogonally order-3 symmetric tensor.We give a geometric landscape analysis of a nonconvex optimization for the best rank-one approximation of orthogonally symmetric tensors.We show that any local minimizer must be a factor in this orthogonally symmetric tensor decomposition,and any other critical points are linear combinations of the factors.Then,we propose a gradient descent algorithm with a carefully designed initialization to solve this nonconvex optimization problem,and we prove that the algorithm converges to the global minimum with high probability for orthogonal decomposable tensors.This result,combined with the landscape analysis,reveals that the greedy algorithm will get the tensor CP low-rank decomposition.Numerical results are provided to verify our theoretical results.展开更多
基金Jian-Feng Cai is partially supported by the National Natural Science Foundation of USA(No.DMS 1418737).
文摘In image restoration,we usually assume that the underlying image has a good sparse approximation under a certain system.Wavelet tight frame system has been proven to be such an efficient system to sparsely approximate piecewise smooth images.Thus,it has been widely used in many practical image restoration problems.However,images from different scenarios are so diverse that no static wavelet tight frame system can sparsely approximate all of themwell.To overcome this,recently,Cai et.al.(Appl Comput Harmon Anal 37:89–105,2014)proposed a method that derives a data-driven tight frame adapted to the specific input image,leading to a better sparse approximation.The data-driven tight frame has been applied successfully to image denoising and CT image reconstruction.In this paper,we extend this data-driven tight frame construction method to multi-channel images.We construct a discrete tight frame system for each channel and assume their sparse coefficients have a joint sparsity.The multi-channel data-driven tight frame construction scheme is applied to joint color and depth image reconstruction.Experimental results show that the proposed approach has a better performance than state-of-the-art joint color and depth image reconstruction approaches.
基金Research supported in part by the National Natural Science Foundation of China under grant 10471027 and Shanghai Education Committee, RGC 7046/03P, 7035/04P, 7045/05P and HKBU FRGs.The authors would like to thank the referees for their useful suggestions.
文摘Newton＇s iteration is modified for the computation of the group inverses of singular Toeplitz matrices. At each iteration, the iteration matrix is approximated by a matrix with a low displacement rank. Because of the displacement structure of the iteration matrix, the matrix-vector multiplication involved in Newton＇s iteration can be done efficiently. We show that the convergence of the modified Newton iteration is still very fast. Numerical results are presented to demonstrate the fast convergence of the proposed method.
文摘In this paper, two framelet based deconvolution algorithms are proposed. The basic idea of framelet based approach is to convert the deconvolution problem to the problem of inpainting in a frame domain by constructing a framelet system with one of the masks being the given （discrete） convolution kernel via the unitary extension principle of [26], as introduced in [6-9] . The first algorithm unifies our previous works in high resolution image reconstruction and infra-red chopped and nodded image restoration, and the second one is a combination of our previous frame-based deconvolution algorithm and the iterative thresholding algorithm given by [14, 16]. The strong convergence of the algorithms in infinite dimensional settings is given by employing proximal forward-backward splitting （PFBS） method. Consequently, it unifies iterative algorithms of infinite and finite dimensional setting and simplifies the proof of the convergence of the aluorithms of [6].
基金supported in part by Hong Kong Research Grant Council General Research Grant Nos.16309518,16309219,16310620,and 16306821supported in part by Hong Kong Research Grant Council General Research Grant Nos.16306415 and 16308518
文摘A fundamental problem in phase retrieval is to reconstruct an unknown signal from a set of magnitude-only measurements.In this work we introduce three novel quotient intensity models(QIMs) based on a deep modification of the traditional intensity-based models.A remarkable feature of the new loss functions is that the corresponding geometric landscape is benign under the optimal sampling complexity.When the measurements ai∈Rn are Gaussian random vectors and the number of measurements m≥Cn,the QIMs admit no spurious local minimizers with high probability,i.e.,the target solution x is the unique local minimizer(up to a global phase) and the loss function has a negative directional curvature around each saddle point.Such benign geometric landscape allows the gradient descent methods to find the global solution x(up to a global phase) without spectral initialization.
基金supported in part by Hong Kong Research Grant Council General Research Grant Nos.16309518,16309219,16310620 and 16306821supported in part by the Hong Kong Research Grant Council General Research Grant Nos.16306415 and 16308518.
文摘A fundamental task in phase retrieval is to recover an unknown signal x∈R^(n) from a set of magnitude-only measurements y_(i)=|〈a_(i),x〉|,i=1,…,m.In this paper,we propose two novel perturbed amplitude models(PAMs)which have a non-convex and quadratic-type loss function.When the measurements a_(i)∈R^(n) are Gaussian random vectors and the number of measurements m≥Cn,we rigorously prove that the PAMs admit no spurious local minimizers with high probability,i.e.,the target solution x is the unique local minimizer(up to a global phase)and the loss function has a negative directional curvature around each saddle point.Thanks to the well-tamed benign geometric landscape,one can employ the vanilla gradient descent method to locate the global minimizer x(up to a global phase)without spectral initialization.We carry out extensive numerical experiments to show that the gradient descent algorithm with random initialization outperforms state-of-the-art algorithms with spectral initialization in empirical success rate and convergence speed.
基金JL was supported by China Postdoctoral Science Foundation grant No.2017M620589JFC was supported in part by Hong Kong Research Grant Council(HKRGC)grants 16300616 and 16306317HK Zhao was supported in part by NSF grants DMS-1418422 and DMS-1622490.
文摘We investigate the problem of robust matrix completion with a fraction of observation corrupted by sparsity outlier noise.We propose an algorithmic framework based on the ADMM algorithm for a non-convex optimization,whose objective function consists of an l1 norm data fidelity and a rank constraint.To reduce the computational cost per iteration,two inexact schemes are developed to replace the most time-consuming step in the generic ADMM algorithm.The resulting algorithms remarkably outperform the existing solvers for robust matrix completion with outlier noise.When the noise is severe and the underlying matrix is ill-conditioned,the proposed algorithms are faster and give more accurate solutions than state-of-the-art robust matrix completion approaches.
文摘Symmetric tensor decomposition is of great importance in applications.Several studies have employed a greedy approach,where the main idea is to first find a best rank-one approximation of a given tensor,and then repeat the process to the residual tensor by subtracting the rank-one component.In this paper,we focus on finding a best rank-one approximation of a given orthogonally order-3 symmetric tensor.We give a geometric landscape analysis of a nonconvex optimization for the best rank-one approximation of orthogonally symmetric tensors.We show that any local minimizer must be a factor in this orthogonally symmetric tensor decomposition,and any other critical points are linear combinations of the factors.Then,we propose a gradient descent algorithm with a carefully designed initialization to solve this nonconvex optimization problem,and we prove that the algorithm converges to the global minimum with high probability for orthogonal decomposable tensors.This result,combined with the landscape analysis,reveals that the greedy algorithm will get the tensor CP low-rank decomposition.Numerical results are provided to verify our theoretical results.
