Search

The nonconvex optimization method has attracted increasing attention due to its excellent ability of promoting sparsity in signal processing, image restoration, and machine learning. In this paper, we consider a new minimization method L1 -ß Lq ((ß, q)-[0, 1]×[1, 8)\(1, 1)) and its applications in signal recovery and image reconstruction because L1 -ß Lq minimization provides an effective way to solve the q-ratio sparsity minimization model. Our main contributions are to establish a convex hull decomposition for L1 -ß Lq and investigate RIP-based conditions for stable signal recovery and image reconstruction by L1 -ß Lq minimization. For one-dimensional signal recovery, our derived RIP condition extends existing results. For two-dimensional image recovery under L1 -ß Lq minimization of image gradients, we provide the error estimate of the resulting optimal solutions in terms of sparsity and noise level, which is missing in the literature. Numerical results of the limited angle problem in computed tomography imaging and image deblurring are presented to validate the efficiency and superiority of the proposed minimization method among the state-of-art image recovery methods. [ABSTRACT FROM AUTHOR]

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]

Nonnegative matrix factorization (NMF) is a popular model in the field of pattern recognition. The aim is to find a low rank approximation for nonnegative matrix M by a product of two nonnegative matrices W and H. In general, NMF is NP-hard to solve while it can be solved efficiently under a separability assumption, which requires that the columns of the factor matrix are some columns of the input matrix M. In this paper, we generalize the separability assumption based on 3-factor NMF (M = P1SP2), and require that S is a submatrix of the input matrix M. We refer to this NMF as a Coseparable NMF (CoS-NMF). In the paper, we discuss and study mathematical properties of CoS-NMF, and present its relationships with other matrix factorizations such as generalized separable NMF, tri-symNMF, biorthogonal trifactorization and CUR decomposition. An optimization method for CoS-NMF is proposed, and an alternating fast gradient method is employed to determine the rows and the columns of M for the submatrix S. Numerical experiments on synthetic data sets, document data sets, and facial data sets are conducted to verify the effectiveness of the proposed CoS-NMF model. By comparison with state-of-the-art methods, the CoS-NMF model performs very well in a coclustering task by finding useful features, and keeps a good approximation to the input data matrix as well. [ABSTRACT FROM AUTHOR]

This paper studies the phase-only reconstruction problem of recovering a complexvalued signal x in Cd from the phase of Ax where A is a given measurement matrix in Cmxd. The reconstruction, if possible, should be up to a positive scaling factor. By using the rank of discriminant matrices, uniqueness conditions are derived to characterize whether the underlying signal can be uniquely reconstructed. We are also interested in the problem of minimal measurement number. We show that at least 2d but no more than 4d - 2 measurements are needed for the reconstruction of all x ∈ Cd, whereas the minimal measurement number is exactly 2d - 1 if we pursue the recovery of almost all signals. Moreover, when adapted to the phase-only reconstruction of x ∈ Rd, our uniqueness conditions are more practical and general than existing ones. Our theoretical results can be straightforwardly extended to affine phase-only reconstruction where the phase of Ax + b is observed for some b ∈ Cm. [ABSTRACT FROM AUTHOR]

The transform-based tensor nuclear norm (TNN) methods have shown good recovery results for tensor completion. However, the TNN methods are based on the single-tube transforms in which transforms are applied to each tube independently. The performance of the single-tube transformbased TNN methods is not good for recovery of missing tubes in multidimensional images (e.g., all the observations are missing in a pixel location of multispectral images). The main aim of this paper is to address this issue by proposing and developing a learnable group-tube transform-based TNN (GTNN) method that can effectively explore the correlation of neighboring tubes by leveraging a learnable group-tube transform. The proposed learnable group-tube transform is a separable three-dimensional transform that consists of a one-dimensional spectral/temporal transform (i.e., single-tube transform) and a two-dimensional spatial transform. Such group-tube transform can effectively explore the correlation of neighboring tubes. Based on the elaborately designed low-rank metric GTNN, we suggest a low-rank tensor completion model. To solve this highly nonconvex model, we design an efficient multiblock proximal alternating minimization algorithm and establish the convergence guarantee. A variety of numerical experiments on real-world multidimensional imaging data including traffic speed data, color images, videos, and multispectral images collectively manifest that the GTNN method outperforms some state-of-the-art TNN methods especially when the observations along tubes are missing. [ABSTRACT FROM AUTHOR]

A transverse wave is a wave in which the particles are displaced perpendicular to the direction of the wave's advance. Examples of transverse waves include ripples on the surface of water and light waves. Polarization is one of the primary properties of transverse waves. Analysis of polarization states can reveal valuable information about the sources. In this paper, we propose a separable low-rank quaternion linear mixing model for polarized signals: we assume each column of the source factor matrix equals a column of the polarized data matrix and refer to the corresponding problem as separable quaternion matrix factorization (SQMF). We discuss some properties of the matrix that can be decomposed by SQMF. To determine the source factor matrix in quaternion space, we propose a heuristic algorithm called quaternion successive projection algorithm (QSPA) inspired by the successive projection algorithm. To guarantee the effectiveness of QSPA, a new normalization operator is proposed for the quaternion matrix. We use a block coordinate descent algorithm to compute nonnegative activation matrix in real number space. We test our method on the applications of polarization image representation and spectro-polarimetric imaging unmixing to verify its effectiveness. [ABSTRACT FROM AUTHOR]

Spherical image processing has been widely applied in many important fields, such as omnidirectional vision for autonomous cars, global climate modeling, and medical imaging. It is nontrivial to extend an algorithm developed for flat images to the spherical ones. In this work, we focus on the challenging task of spherical image inpainting with a deep learning-based regularizer. Instead of a naive application of existing models for planar images, we employ a fast directional spherical Haar framelet transform and develop a novel optimization framework based on a sparsity assumption of the framelet transform. Furthermore, by employing progressive encoder-decoder architecture, a new and better-performed deep CNN denoiser is carefully designed and works as an implicit regularizer. Finally, we use a plug-and-play method to handle the proposed optimization model, which can be implemented efficiently by training the CNN denoiser prior. Numerical experiments are conducted and show that the proposed algorithms can greatly recover damaged spherical images and achieve the best performance over purely using a deep learning denoiser and a plug-and-play model. [ABSTRACT FROM AUTHOR]

Image denoising is one of the most important tasks in image processing. In this paper, we study image denoising methods by using similar patches which have low-rank covariance matrices to recover an underlying image which is corrupted by additive Gaussian noise. In order to enhance global patch-matching results, we make use of a Gaussian mixture model with an auxiliary image to determine different groups of patches. The auxiliary image is an output of BM3D. The noisy version of covariance matrix is formed by each group of patches from the given noisy image. Its low-rank version can be estimated by using covariance matrix nuclear norm minimization, and the resulting denoised image can be obtained. Experimental results are reported to show that the proposed method outperforms the state-of-the-art denoising methods, including testing deep learning methods, in the peak signal-to-noise ratio, structural similarity values, and visual quality. [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 color image inpainting as a pure quaternion matrix completion problem. In the literature, the theoretical guarantee for quaternion matrix completion is not well established. Our main aim is to propose a new minimization problem with an objective combining nuclear norm and a quadratic loss weighted among three channels. To fill the theoretical vacancy, we obtain the error bound in both clean and corrupted regimes, which relies on some new results of quaternion matrices. A general Gaussian noise is considered in robust completion where all observations are corrupted. Motivated by the error bound, we propose to handle unbalanced or correlated noise via a cross-channel weight in the quadratic loss, with the main purpose of rebalancing noise level or removing noise correlation. Extensive experimental results on synthetic and color image data are presented to confirm and demonstrate our theoretical findings. [ABSTRACT FROM AUTHOR]

Color image enhancement is one of the most important tasks in image processing. In this paper, we focus on the red and/or blue attenuation problem that arises in underwater image enhancement. We propose and develop a novel spatial color compensation model based on saturation-value total variation (SV-TV). In the proposed model, the compensation of the red and/or blue attenuation is achieved by adding a fraction of the green channel to the red and/or blue channel. The fraction is determined by a spatially varying function, which is controlled by the TV regularization. In order to avoid overcompensation and too many color artifacts, we make use of the SV-TV to regularize the objective compensation result. We numerically apply the proximal alternating linearized minimization to solve the proposed minimization problem, and we give the convergence analysis of the proposed algorithm. Numerical examples are presented to demonstrate that the performance of the proposed color compensation model is better than that of other testing methods in terms of visual quality and certain criteria, such as peak signal-to-noise ratio (PSNR), structure similarity (SSIM), and CIEde2000 color difference. [ABSTRACT FROM AUTHOR]

Transformed L1 (TL1) regularization has been shown to have comparable signal recovery capability with L1 L2 regularization and L1/L2 regularization, regardless of whether the measurement matrix satisfies the restricted isometry property (RIP). In the spirit of the TL1 method, we introduce a transformed total variation (TTV) minimization model to investigate robust image recovery from a certain number of noisy measurements by the proposed TTV minimization model in this paper. An optimal error bound, up to a logarithmic factor, of robust image recovery from compressed measurements via the TTV minimization model is established, and the RIP based condition is improved compared with total variation (TV) minimization. Numerical results of image reconstruction demonstrate our theoretical results and illustrate the efficiency of the TTV minimization model among state-of-the-art methods. Empirically, the error bound between the reconstructed image and the original image is shown to be better than that produced by TV minimization. [ABSTRACT FROM AUTHOR]

In this paper, we first give new model formulations for computing arbitrary generalized singular value of a Grassmann matrix pair or a real matrix pair. In these new formulations, we need to solve matrix optimization problems with unitary constraints or orthogonal constraints. We propose a geometric inexact Newton--conjugate gradient (Newton-CG) method for solving the resulting matrix optimization problems. Under some mild assumptions, we establish the global and quadratic convergence of the proposed method for the complex case. Some numerical examples are given to illustrate the effectiveness and high accuracy of the proposed method. [ABSTRACT FROM AUTHOR]

In [McDonald, Pestana, and Wathen, SIAM J. Sci. Comput., 40 (2018), pp. A1012--A1033], a block circulant preconditioner is proposed for all-at-once linear systems arising from evolutionary partial differential equations, in which the preconditioned matrix is proven to be diagonalizable and to have identity-plus-low-rank decomposition in the case of the heat equation. In this paper, we generalize the block circulant preconditioner by introducing a small parameter ϵ>0 into the top-right block of the block circulant preconditioner. The implementation of the generalized preconditioner requires the same computational complexity as that of the block circulant one. Theoretically, we prove that (i) the generalization preserves the diagonalizability and the identity-plus-low-rank decomposition; (ii) all eigenvalues of the new preconditioned matrix are clustered at 1 for sufficiently small\epsilon; (iii) GMRES method for the preconditioned system has a linear convergence rate independent of size of the linear system when\epsilon is taken to be smaller than or comparable to square root of time-step size. Numerical results are reported to confirm the efficiency of the proposed preconditioner and to show that the generalization improves the performance of block circulant preconditioner. [ABSTRACT FROM AUTHOR]

In practical applications, incremental tensors are very common: only a portion of tensor data is available, and new data are arriving in the next time step or continuously over time. To handle this type of tensors time-saving algorithms are required for online computation. In this paper, we consider incremental CP ( CANDECOMP/PARAFAC ) decomposition, which requires one to update the CP decomposition after new tensor data, together with the exiting tensor, are ready for analysis. There exist several incremental CP decomposition algorithms, but almost all of these algorithms assume that the number of CP decomposition components remains fixed in the incremental process. The main contribution of this paper is the study of how to add components in the incremental CP decomposition. We derive the coordinate representation of the incremental CP decomposition with respect to a special basis and show related properties of tensor rank and the uniqueness of such incremental CP decomposition. Under the framework of this representation, the proposed method can be solved by using an alternating minimization algorithm. Numerical examples are presented to show the good performance of the proposed algorithms in terms of computational time and data fitting compared with existing methods. [ABSTRACT FROM AUTHOR]

The main aim of this paper is to develop the quaternion generalized minimal residual method (QGMRES) for solving quaternion linear systems. Quaternion linear systems arise fromthree-dimensional or color imaging filtering problems. The proposed quaternion Arnoldi procedure can preserve quaternion Hessenberg form during the iterations. The main advantage is that the storage of the proposed iterative method can be reduced by comparing with the Hessenberg form constructed by the classical GMRES iterations for the real representation of quaternion linear systems. The convergence of the proposed QGMRES is also established. Numerical examples are presented to demonstrate the effectiveness of the proposed QGMRES compared with the traditional GMRES in terms of storage and computing time [ABSTRACT FROM AUTHOR]

The l1-l2 regularization is a popular nonconvex yet Lipschitz continuous metric, which has been widely used in signal and image processing. The theory for the l1-l2 minimization method shows that it has superior sparse recovery performance over the classical l1 minimization method. The motivation and major contribution of this paper is to provide a positive answer to the open problem posed in [T.-H. Ma, Y. Lou, and T.-Z. Huang, SIAM J. Imaging Sci., 10 (2017), pp. 1346-1380] about the sufficient conditions that can be sharpened for the l1-l2 minimization method. The novel technique used in our analysis of the l1-l2 minimization method is a crucial sparse representation adapted to the l1-l2 metric which is different from the other state-of-the-art works in the context of the l1-l2 minimization method. The new restricted isometry property (RIP) analysis is better than the existing RIP based conditions to guarantee the exact and stable recovery of signals. [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]

Color image restoration is one of the important tasks in color image processing. Covariant differentiation has been applied to handle vector bundles arising from color images in the red, green, blue (RGB) color space. However, there are strong correlations among these three channels, and color image regularization in RGB color space may not be effective enough. The main aim of this paper is to study vector bundles of color images in saturation-value color space and to develop color image regularization models based on vector bundles in saturation-value color space. We develop the saturation-value metric of a vector bundle of R5-valued functions, and we generalize the vectorial total variation and the vector bundle-valued total variation in saturation-value color space based on the saturation-value metric via the transformation between RGB color space and saturation-value color space. We then develop a saturation-value total variation regularization on vector bundles. We study color image restoration models by using such total variation, and show numerical examples that the proposed color image restoration model outperforms existing methods in terms of visual quality, peak signal-to-noise ratio, and structural similarity. [ABSTRACT FROM AUTHOR]

Quaternion matrices are employed successfully in many color image processing applications. In particular, a pure quaternion matrix can be used to represent red, green, and blue channels of color images. A low-rank approximation for a pure quaternion matrix can be obtained by using the quaternion singular value decomposition. However, this approximation is not optimal in the sense that the resulting low-rank approximation matrix may not be pure quaternion, i.e., the low-rank matrix contains a real component which is not useful for the representation of a color image. The main contribution of this paper is to find an optimal rank-r pure quaternion matrix approximation for a pure quaternion matrix (a color image). Our idea is to use a pro jection on a low-rank quaternion matrix manifold and a projection on a quaternion matrix with zero real component, and develop an alternating pro jections algorithm to find such optimal low-rank pure quaternion matrix approximation. The convergence of the pro jection algorithm can be established by showing that the low-rank quaternion matrix manifold and the zero real component quaternion matrix manifold has a nontrivial intersection point. Numerical examples on synthetic pure quaternion matrices and color images are presented to illustrate the pro jection algorithm can find optimal low-rank pure quaternion approximation for pure quaternion matrices or color images. [ABSTRACT FROM AUTHOR]

In this paper, we consider an inverse problem with quasi-boundary value regularization for recovering a source term of the time fractional diffusion equations from the final observation data. In particular, a two-by-two block linear system arising from the problem is studied. We propose a fast preconditioning technique by approximating the Schur complement in the system using a product of some factors, motivated by an approximate diagonalization of one of the blocks. The eigenvalues of the preconditioned system are shown to be clustered around 1, and the fast convergence of the methods is guaranteed theoretically. We also present an approach for selecting the regularization parameter of the quasi-boundary value method. Numerical experiments are carried out to demonstrate the effectiveness of our method. [ABSTRACT FROM AUTHOR]

In this paper, we study the Crank-Nicolson alternative direction implicit (ADI) method for two-dimensional Riesz space-fractional diffusion equations with nonseparable coefficients. Existing ADI methods are only shown to be unconditional stable when coefficients are some special separable functions. The main contribution of this paper is to show under mild assumptions the unconditional stability of the proposed Crank-Nicolson ADI method in discrete l² norm and the consistency of cross perturbation terms arising from the Crank-Nicolson ADI method. Also, we demonstrate that several consistent spatial discretization schemes satisfy the required assumptions. Numerical results are presented to examine the accuracy and the efficiency of the proposed ADI methods. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of low-rank tensor recovery from limited sampling with noisy observations for third-order tensors. A tensor nuclear norm method based on a convex relaxation of the tubal rank of a tensor has been used and studied for tensor completion. In this paper, we propose to incorporate a corrected term in the tensor nuclear norm method for tensor completion. Theoretically, we provide a nonasymptotic error bound of the corrected tensor nuclear norm model for low-rank tensor completion. Moreover, we develop and establish the convergence of a symmetric Gauss-Seidel based multiblock alternating direction method of multipliers to solve the proposed correction model. Extensive numerical examples on both synthetic and real-world data are presented to validate the superiority of the proposed model over several state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Color image restoration is one of the important tasks in color image processing. Total variation regularizaton was proposed and employed for the recovery of edges in a grayscale image. In the literature, there are several methods for extension of total variation regularization for color images, for example, based on color channel coupling and tensor regularization. The main contribution of this paper is to propose and develop a new saturation-value (SV) color total variation regularization in the hue, saturation, amd value color space instead of in the original red, green, and blue color space. The development of this SV total variation can be studied via the representation of color images in the quaternion framework for color edge detection. We will investigate the properties of the SV total variation regularization and the resulting optimization model for color image restoration. Numerical examples are presented to demonstrate that the performance of the new SV total variation is better than that of existing color image total variation methods in terms of some criteria such as PSNR, SSIM, and S-CIELAB error. [ABSTRACT FROM AUTHOR]

In this paper, we study orthogonal nonnegative matrix factorization. We demonstrate the coefficient matrix can be sparse and low-rank in the orthogonal nonnegative matrix factorization. By using these properties, we propose to use a sparsity and nuclear norm minimization for the factorization and develop a convex optimization model for finding the coefficient matrix in the factorization. Numerical examples including synthetic and real-world data sets are presented to illustrate the effectiveness of the proposed algorithm and demonstrate that its performance is better than other testing methods. [ABSTRACT FROM AUTHOR]

In this paper, we propose and study a nonconvex data fitting term and a total variation regularization term for image restoration with impulse noise removal. The proposed model is different from existing image restoration models where the data fitting term is based on the ℓ1- or ℓ2-norm, and the regularization term is based on the total variation, ℓ1-norm, or some nonconvex functions. Theoretically, we analyze the properties of minimizers of the proposed objective function with the nonconvex data fitting term and the total variation regularization term. We show that minimizers can preserve piecewise constant regions or match with the data points perfectly. This property is particularly useful for impulse noise removal. The proposed image restoration model can be solved by the proximal linearized minimization algorithm, and the global convergence of the iterative algorithm can also be established according to Kurdyka–Lojasiewicz property. The performance of the proposed model is tested for image restoration with salt-and-pepper impulse noise or random-valued impulse noise. We demonstrate that the restored images by the proposed Nonconvex-TV model are better (in terms of PSNR and visual quality) than those by the other existing data fitting plus regularization models, including ℓ1 plus total variation (L1TV) and ℓ1 plus nonconvex (L1Nonconvex) methods. [ABSTRACT FROM AUTHOR]

Data assimilation is a process used to fuse information from priors, observations of nature, and numerical models, in order to obtain best estimates of the parameters or state of a physical system of interest. Presence of large errors in some observational data, e.g., data collected from a faulty instrument, negatively affect the quality of the overall assimilation results. This work develops a systematic framework for robust data assimilation. The new algorithms continue to produce good estimates of parameters or state in the presence of observation outliers. The approach is based on replacing the traditional L2 norm formulation of data assimilation problems with formulations based on L1 and Huber norms. Numerical experiments using the Lorenz-96 and the shallow water on the sphere models illustrate how the new algorithms outperform traditional data assimilation approaches in the presence of data outliers. [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 Birkhoff-von Neumann theorem for a class of multistochastic tensors. In particular, we give a necessary and sufficient condition such that a multistochastic tensor is a convex combination of finitely many permutation tensors. It is well-known that extreme points in the set of doubly stochastic matrices are just permutation matrices. However, we find that extreme points in the set of multistochastic tensors are not just permutation tensors. We provide the other types of tensors contained in the set of extreme points. [ABSTRACT FROM AUTHOR]