Search

This paper studies deep neural networks for solving extremely large linear systems arising from high-dimensional problems. Because of the curse of dimensionality, it is expensive to store both the solution and right-hand side vector in such extremely large linear systems. Our idea is to employ a neural network to characterize the solution with many fewer parameters than the size of the solution under a matrix-free setting. We present an error analysis of the proposed method, indicating that the solution error is bounded by the condition number of the matrix and the neural network approximation error. Several numerical examples from partial differential equations, queueing problems, and probabilistic Boolean networks are presented to demonstrate that the solutions of linear systems can be learned quite accurately. [ABSTRACT FROM AUTHOR]

In this paper, we study deep neural networks (DNNs) for solving high-dimensional evolution equations with oscillatory solutions. Different from deep least-squares methods that deal with time and space variables simultaneously, we propose a deep adaptive basis Galerkin (DABG) method which employs the spectral-Galerkin method for time variable by a tensor-product basis for oscillatory solutions and the deep neural network method for high-dimensional space variables. The proposed method can lead to a linear system of differential equations having unknown DNNs that can be trained via the loss function. We establish a posteriori estimates of the solution error which is bounded by the minimal loss function and the term O(N-m), where N is the number of basis functions and m characterizes the regularity of the equation, and show that if the true solution is a Barron-type function, the error bound converges to zero as M = O(Np) approaches to infinity where M is the width of the used networks and p is a positive constant. Numerical examples, including high-dimensional linear parabolic and hyperbolic equations, and a nonlinear Allen--Cahn equation are presented to demonstrate that the performance of the proposed DABG method is better than that of existing DNNs. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel method for solving high-dimensional spectral fractional Laplacian equations. Using the Caffarelli--Silvestre extension, the d-dimensional spectral fractional equation is reformulated as a regular partial differential equation of dimension d+1. We transform the extended equation as a minimal Ritz energy functional problem and search for its minimizer in a special class of deep neural networks. Moreover, based on the approximation property of networks, we establish estimates on the error made by the deep Ritz method. Numerical results are reported to demonstrate the effectiveness of the proposed method for solving fractional Laplacian equations up to 10 dimensions. Technically, in this method, we design a special network-based structure to adapt to the singularity and exponential decaying of the true solution. Also, a hybrid integration technique combining the Monte Carlo method and sinc quadrature is developed to compute the loss function with higher accuracy. [ABSTRACT FROM AUTHOR]

In this paper, we study nonnegative tensor data and propose an orthogonal nonnegative Tucker decomposition (ONTD). We discuss some properties of ONTD and develop a convex relaxation algorithm of the augmented Lagrangian function to solve the optimization problem. The convergence of the algorithm is given. We employ ONTD on the image data sets from the real world applications including face recognition, image representation, and hyperspectral unmixing. Numerical results are shown to illustrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The phase retrieval problem has drawn considerable attention, as many optical detection devices can only measure magnitudes of the Fourier transform of the underlying object (signal or image). This paper addresses the phase retrieval problem from incomplete data, where only partial magnitudes of Fourier transform are obtained. In particular, we consider structured illuminated patterns in holography and find that noninteger values used in designing such patterns often yield better reconstruction than the conventional integer-valued ones. Furthermore, we demonstrate theoretically and numerically that three diffracted sets of (complete) magnitude data are sufficient to recover the object. To compensate for incomplete information, we incorporate a total variation regularization a priori to guarantee that the reconstructed image satisfies some desirable properties. The proposed model can be solved efficiently by an alternative directional multiplier method with provable convergence. Numerical experiments validate the theoretical finding and demonstrate the effectiveness of the proposed method in recovering objects from noisy and incomplete data. [ABSTRACT FROM AUTHOR]

In this paper, we study the linear systems arising from the discretization of timedependent space-fractional diffusion equations. By using a finite difference discretization scheme for the time derivative and a finite volume discretization scheme for the space-fractional derivative, Toeplitz-like linear systems are obtained. We propose using the approximate inverse-circulant preconditioner to deal with such Toeplitz-like matrices, and we show that the spectra of the corresponding preconditioned matrices are clustered around 1. Experimental results on time-dependent and space-fractional diffusion equations are presented to demonstrate that the preconditioned Krylov subspace methods converge very quickly. [ABSTRACT FROM AUTHOR]

Over the past few decades, much attention has been drawn to large-scale incremental data analysis, where researchers are faced with huge amounts of high-dimensional data acquired incrementally. In such a case, conventional algorithms that compute the result from scratch whenever a new sample comes are highly inefficient. To conquer this problem, we propose a new incremental algorithm incremental regularized least squares (IRLS) that incrementally computes the solution to the regularized least squares (RLS) problem with multiple columns on the right-hand side. More specifically, for an RLS problem with c (c > 1) columns on the right-hand side, we update its unique solution by solving an RLS problem with a single column on the right-hand side whenever a new sample arrives, instead of solving an RLS problem with c columns on the right-hand side from scratch. As a direct application of IRLS, we consider the supervised dimensionality reduction of large-scale data and focus on linear discriminant analysis (LDA). We first propose a new batch LDA model that is closely related to the RLS problem, and then apply IRLS to develop a new incremental LDA algorithm. Experimental results on real-world datasets demonstrate the effectiveness and efficiency of our algorithms. [ABSTRACT FROM AUTHOR]

The fractional diffusion equation is discretized by an implicit finite difference scheme with the shifted Grünwald formula, which is unconditionally stable. The coefficient matrix of the discretized linear system is equal to the sum of a scaled identity matrix and two diagonal-times-Toeplitz matrices. Standard circulant preconditioners may not work for such Toeplitz-like linear systems. The main aim of this paper is to propose and develop approximate inverse preconditioners for such Toeplitz-like matrices. An approximate inverse preconditioner is constructed to approximate the inverses of weighted Toeplitz matrices by circulant matrices, and then combine them together row-by-row. Because of Toeplitz structure, both the discretized coefficient matrix and the preconditioner can be implemented very efficiently by using fast Fourier transforms. Theoretically, we show that the spectra of the resulting preconditioned matrices are clustered around one. Thus Krylov subspace methods with the proposed preconditioner converge very fast. Numerical examples are given to demonstrate the effectiveness of the proposed preconditioner and show that its performance is better than the other testing preconditioners. [ABSTRACT FROM AUTHOR]

In this paper, we study the total variation structured total least squares method for image restoration. In the image restoration problem, the point spread function is corrupted by errors. In the model, we study the objective function by minimizing two variables: the restored image and the estimated error of the point spread function. The proposed objective function consists of the data-fitting term containing these two variables, the magnitude of error and the total variation regularization of the restored image. By making use of the structure of the objective function, an efficient alternating minimization scheme is developed to solve the proposed model. Numerical examples are also presented to demonstrate the effectiveness of the proposed model and the efficiency of the numerical scheme. [ABSTRACT FROM AUTHOR]

We propose a new family of cost functions for signal and image recovery: they are composed of l1 data fitting terms combined with concave regularization. We exhibit when and how to employ such cost functions. Our theoretical results show that the minimizers of these cost functions are such that each one of their entries is involved either in an exact data fitting component or in a null component of the regularization part. This is a strong and particular property that can be useful for various image recovery problems. The minimization of such cost functions presents a computational challenge. We propose a fast minimization algorithm to solve this numerical problem. The experimental results show the effectiveness of the proposed algorithm. All illustrations and numerical experiments give a flavor of the possibilities offered by the minimizers of this new family of cost functions in solving specialized image processing tasks. [ABSTRACT FROM AUTHOR]

Image restoration problems are often solved by finding the minimizer of a suitable objective function consisting of a data-fitting term and a regularization term. In this paper, we consider the data-fitting term measured in the ℓ1 norm to handle non-Gaussian additive noise and the regularization term given by the total variation (TV) to restore image edges. We propose a new algorithm for this image restoration problem by making use of new variables to modify the data-fitting term and the TV regularization term. An alternating minimization method based on the new formulation is employed to restore blurred and noisy images. Our experimental results show that the quality of restored images by the proposed method is competitive with those restored by the other tested methods. We also show the convergence of the alternating minimization algorithm and demonstrate that the proposed algorithm is very efficient. [ABSTRACT FROM AUTHOR]

In this paper, we propose iterative algorithms for solving image restoration problems. The iterative algorithms are based on decoupling of deblurring and denoising steps in the restoration process. In the deblurring step, an efficient deblurring method using fast transforms can be employed. In the denoising step, effective methods such as the wavelet shrinkage denoising method or the total variation denoising method can be used. The main advantage of this proposal is that the resulting algorithms can be very efficient and can produce better restored images in visual quality and signalto-noise ratio than those by the restoration methods using the combination of a data-fitting term and a regularization term. The convergence of the proposed algorithms is shown in the paper. Numerical examples are also given to demonstrate the effectiveness of these algorithms. [ABSTRACT FROM AUTHOR]

We study the Newton method and a fixed-point method for solving the system of nonlinear equations arising from the Sinc--Galerkin discretization of the Burgers equations. In each step of the Newton method or the fixed-point method, a structured subsystem of linear equations is obtained and needs to be solved numerically. In this paper, preconditioning techniques are applied to solve such linear subsystems. The bounds for eigenvalues of the preconditioned matrices are derived and numerical examples are given to illustrate the effectiveness of the proposed methods. We also find that a combination of the Newton/fixed-point iteration with the preconditioned GMRES method is quite efficient for the Sinc--Galerkin discretization of the Burgers equations. [ABSTRACT FROM AUTHOR]

The problem of 3×3 color mixing image restoration is considered. The blurring matrices, as well as the observed image, are contaminated by noise; therefore the total least squares (TLS) method is employed to restore the original image. Since the blurring matrices are also structured, we apply the structured total least squares (STLS) method [J. B. Rosen, H. Park, and J. Glick, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 110–126]. The blurring matrices are generally ill conditioned; thus Tikhonov's regularization is used to stabilize the solution. Since Neumann boundary conditions are used in the restoration process, the discrete cosine transform (DCT) based preconditioner is effective for the linear systems encountered in our STLS algorithm. [ABSTRACT FROM AUTHOR]

Image restoration problems are often solved by finding the minimizer of a suitable objective function. Usually this function consists of a data-fitting term and a regularization term. For the least squares solution, both the data-fitting and the regularization terms are in the ℓ2 norm. In this paper, we consider the least absolute deviation (LAD) solution and the least mixed norm (LMN) solution. For the LAD solution, both the data-fitting and the regularization terms are in the ℓ1 norm. For the LMN solution, the regularization term is in the ℓ1 norm but the data-fitting term is in the ℓ2 norm. Since images often have nonnegative intensity values, the proposed algorithms provide the option of taking into account the nonnegativity constraint. The LMN and LAD solutions are formulated as the solution to a linear or quadratic programming problem which is solved by interior point methods. At each iteration of the interior point method, a structured linear system must be solved. The preconditioned conjugate gradient method with factorized sparse inverse preconditioners is employed to solve such structured inner systems. Experimental results are used to demonstrate the effectiveness of our approach. We also show the quality of the restored images, using the minimization of mixed ℓ2-ℓ1 and ℓ1-ℓ1 norms, is better than that using only the ℓ2 norm. [ABSTRACT FROM AUTHOR]

We address the minimization of regularized convex cost functions which are customarily used for edge-preserving restoration and reconstruction of signals and images. In order to accelerate computation, the multiplicative and the additive half-quadratic reformulation of the original cost-function have been pioneered in Geman and Reynolds [IEEE Trans. Pattern Anal. Machine Intelligence, 14 (1992), pp. 367--383] and Geman and Yang IEEE Trans. Image Process., 4 (1995), pp. 932--946]. The alternate minimization of the resultant (augmented) cost-functions has a simple explicit form. The goal of this paper is to provide a systematic analysis of the convergence rate achieved by these methods. For the multiplicative and additive half-quadratic regularizations, we determine their upper bounds for their root-convergence factors. The bound for the multiplicative form is seen to be always smaller than the bound for the additive form. Experiments show that the number of iterations required for convergence for the multiplicative form is always less than that for the additive form. However, the computational cost of each iteration is much higher for the multiplicative form than for the additive form. The global assessment is that minimization using the additive form of half-quadratic regularization is faster than using the multiplicative form. When the additive form is applicable, it is hence recommended. Extensive experiments demonstrate that in our MATLAB implementation, both methods are substantially faster (in terms of computational times) than the standard MATLAB Optimization Toolbox routines used in our comparison study. [ABSTRACT FROM AUTHOR]