On the fast Lanczos method for computation of eigenvalues of Hankel matrices using multiprecision arithmetics

The use of the fast Fourier transform (FFT) accelerates Lanczos tridiagonalisation method for Hankel and Toeplitz matrices by reducing the complexity of matrix-vector multiplication. In multiprecision arithmetics, the FFT has overheads that make it less competitive compared with alternative methods when the accuracy is over 10000 decimal places. We studied two alternative Hankel matrix-vector multiplication methods based on multiprecision number decomposition and recursive Karatsuba-like multiplication, respectively. The first method was uncompetitive because of huge precision losses, while the second turned out to be five to 14 times faster than FFT in the ranges of matrix sizes up to n = 8192 and working precision of b = 32768 bits we were interested in. We successfully applied our approach to eigenvalues calculations to studies of spectra of matrices that arise in research on Riemann zeta function. The recursive matrix-vector multiplication significantly outperformed both the FFT and the traditional multiplication in these studies.

Parallel matrix inversion techniques

In this paper, we present techniques for inverting sparse, symmetric and positive definite matrices on parallel and distributed computers. We propose two algorithms, one for SIMD implementation and the other for MIMD implementation. These algorithms are modified versions of Gaussian elimination and they take into account the sparseness of the matrix. Our algorithms perform better than the general parallel Gaussian elimination algorithm. In order to demonstrate the usefulness of our technique, we implemented the snake problem using our sparse matrix algorithm. Our studies reveal that the proposed sparse matrix inversion algorithm significantly reduces the time taken for obtaining the solution of the snake problem. In this paper, we present the results of our experimental work.

A novel monotonic fixed-point algorithm for l1-regularized least square vector and matrix problem

Least square problem with l₁ regularization has been proposed as a promising method for sparse signal reconstruction (e.g., basis pursuit de-noising and compressed sensing) and feature selection (e.g., the Lasso algorithm) in signal processing, statistics, and related fields. These problems can be cast as l₁-regularized least-square program (LSP). In this paper, we propose a novel monotonic fixed point method to solve large-scale l₁-regularized LSP. And we also prove the stability and convergence of the proposed method. Furthermore we generalize this method to least square matrix problem and apply it in nonnegative matrix factorization (NMF). The method is illustrated on sparse signal reconstruction, partner recognition and blind source separation problems, and the method tends to convergent faster and sparser than other l₁-regularized algorithms.

Blind Spectral Unmixing Based on Sparse Nonnegative Matrix Factorization

Nonnegative matrix factorization (NMF) is a widely used method for blind spectral unmixing (SU), which aims at obtaining the endmembers and corresponding fractional abundances, knowing only the collected mixing spectral data. It is noted that the abundance may be sparse (i.e., the endmembers may be with sparse distributions) and sparse NMF tends to lead to a unique result, so it is intuitive and meaningful to constrain NMF with sparseness for solving SU. However, due to the abundance sum-to-one constraint in SU, the traditional sparseness measured by L0/L1-norm is not an effective constraint any more. A novel measure (termed as S-measure) of sparseness using higher order norms of the signal vector is proposed in this paper. It features the physical significance. By using the S-measure constraint (SMC), a gradient-based sparse NMF algorithm (termed as NMF-SMC) is proposed for solving the SU problem, where the learning rate is adaptively selected, and the endmembers and abundances are simultaneously estimated. In the proposed NMF-SMC, there is no pure index assumption and no need to know the exact sparseness degree of the abundance in prior. Yet, it does not require the preprocessing of dimension reduction in which some useful information may be lost. Experiments based on synthetic mixtures and real-world images collected by AVIRIS and HYDICE sensors are performed to evaluate the validity of the proposed method.

Mixing Matrix Estimation From Sparse Mixtures With Unknown Number of Sources

In blind source separation, many methods have been proposed to estimate the mixing matrix by exploiting sparsity. However, they often need to know the source number a priori, which is very inconvenient in practice. In this paper, a new method, namely nonlinear projection and column masking (NPCM), is proposed to estimate the mixing matrix. A major advantage of NPCM is that it does not need any knowledge of the source number. In NPCM, the objective function is based on a nonlinear projection and its maxima just correspond to the columns of the mixing matrix. Thus a column can be estimated first by locating a maximum and then deflated by a masking operation. This procedure is repeated until the evaluation of the objective function decreases to zero dramatically. Thus the mixing matrix and the number of sources are estimated simultaneously. Because the masking procedure may result in some small and useless local maxima, particle swarm optimization (PSO) is introduced to optimize the objective function. Feasibility and efficiency of PSO are also discussed. Comparative experimental results show the efficiency of NPCM, especially in the cases where the number of sources is unknown and the sources are relatively less sparse.

Sparse representation with multi-manifold analysis for texture classification from few training images

Texture classification is one of the most important tasks in computer vision field and it has been extensively investigated in the last several decades. Previous texture classification methods mainly used the template matching based methods such as Support Vector Machine and k-Nearest-Neighbour for classification. Given enough training images the state-of-the-art texture classification methods could achieve very high classification accuracies on some benchmark databases. However, when the number of training images is limited, which usually happens in real-world applications because of the high cost of obtaining labelled data, the classification accuracies of those state-of-the-art methods would deteriorate due to the overfitting effect. In this paper we aim to develop a novel framework that could correctly classify textural images with only a small number of training images. By taking into account the repetition and sparsity property of textures we propose a sparse representation based multi-manifold analysis framework for texture classification from few training images. A set of new training samples are generated from each training image by a scale and spatial pyramid, and then the training samples belonging to each class are modelled by a manifold based on sparse representation. We learn a dictionary of sparse representation and a projection matrix for each class and classify the test images based on the projected reconstruction errors. The framework provides a more compact model than the template matching based texture classification methods, and mitigates the overfitting effect. Experimental results show that the proposed method could achieve reasonably high generalization capability even with as few as 3 training images, and significantly outperforms the state-of-the-art texture classification approaches on three benchmark datasets. © 2014 Elsevier B.V. All rights reserved.

Enabling efficient publicly verifiable outsourcing computation for matrix multiplication

Outsourcing heavy computational tasks to remote cloud server, which accordingly significantly reduce the computational burden at the end hosts, represents an effective and practical approach towards extensive and scalable mobile applications and has drawn increasing attention in recent years. However, due to the limited processing power of the end hosts yet the keen privacy concerns on the outsourced data, it is vital to ensure both the efficiency and security of the outsourcing computation in the cloud computing. In this paper, we address the issue by developing a publicly verifiable outsourcing computation proposal. In particular, considering a large amount of applications of matrix multiplication in large datasets and image processing, we propose a publicly verifiable outsourcing computation scheme for matrix multiplication in the amortized model. Security analysis demonstrates that the proposed scheme is provable secure by blinding input and output in a simple way. By comparing the developed scheme with existing proposals, we show that our proposal is more efficient in terms of functionality, as well as the computation, communication and storage overhead.

A fast non-smooth nonnegative matrix factorization for learning sparse representation

Nonnegative matrix factorization (NMF) is a hot topic in machine learning and data processing. Recently, a constrained version, non-smooth NMF (NsNMF), shows a great potential in learning meaningful sparse representation of the observed data. However, it suffers from a slow linear convergence rate, discouraging its applications to large-scale data representation. In this paper, a fast NsNMF (FNsNMF) algorithm is proposed to speed up NsNMF. In the proposed method, it first shows that the cost function of the derived sub-problem is convex and the corresponding gradient is Lipschitz continuous. Then, the optimization to this function is replaced by solving a proximal function, which is designed based on the Lipschitz constant and can be solved through utilizing a constructed fast convergent sequence. Due to the usage of the proximal function and its efficient optimization, our method can achieve a nonlinear convergence rate, much faster than NsNMF. Simulations in both computer generated data and the real-world data show the advantages of our algorithm over the compared methods.

Multi-scale local pattern co-occurrence matrix for textural image classification

Textural image classification technologies have been extensively explored and widely applied in many areas. It is advantageous to combine both the occurrence and spatial distribution of local patterns to describe a texture. However, most existing state-of-the-art approaches for textural image classification only employ the occurrence histogram of local patterns to describe textures, without considering their co-occurrence information. And they are usually very time-consuming because of the vector quantization involved. Moreover, those feature extraction paradigms are implemented at a single scale. In this paper we propose a novel multi-scale local pattern co-occurrence matrix (MS_LPCM) descriptor to characterize textural images through four major steps. Firstly, Gaussian filtering pyramid preprocessing is employed to obtain multi-scale images; secondly, a local binary pattern (LBP) operator is applied on each textural image to create a LBP image; thirdly, the gray-level co-occurrence matrix (GLCM) is utilized to extract local pattern co-occurrence matrix (LPCM) from LBP images as the features; finally, all LPCM features from the same textural image at different scales are concatenated as the final feature vectors for classification. The experimental results on three benchmark databases in this study have shown a higher classification accuracy and lower computing cost as compared with other state-of-the-art algorithms.

Nonnegative blind source separation by sparse component analysis based on determinant measure

The problem of nonnegative blind source separation (NBSS) is addressed in this paper, where both the sources and the mixing matrix are nonnegative. Because many real-world signals are sparse, we deal with NBSS by sparse component analysis. First, a determinant-based sparseness measure, named D-measure, is introduced to gauge the temporal and spatial sparseness of signals. Based on this measure, a new NBSS model is derived, and an iterative sparseness maximization (ISM) approach is proposed to solve this model. In the ISM approach, the NBSS problem can be cast into row-to-row optimizations with respect to the unmixing matrix, and then the quadratic programming (QP) technique is used to optimize each row. Furthermore, we analyze the source identifiability and the computational complexity of the proposed ISM-QP method. The new method requires relatively weak conditions on the sources and the mixing matrix, has high computational efficiency, and is easy to implement. Simulation results demonstrate the effectiveness of our method.

Cumulative restricted Boltzmann machines for ordinal matrix data analysis

Ordinal data is omnipresent in almost all multiuser-generated feedback - questionnaires, preferences etc. This paper investigates modelling of ordinal data with Gaussian restricted Boltzmann machines (RBMs). In particular, we present the model architecture, learning and inference procedures for both vector-variate and matrix-variate ordinal data. We show that our model is able to capture latent opinion profile of citizens around the world, and is competitive against state-of-art collaborative filtering techniques on large-scale public datasets. The model thus has the potential to extend application of RBMs to diverse domains such as recommendation systems, product reviews and expert assessments.

Sparse Representations of Image via Overcomplete Dictionary Learned by Adaptive Non-orthogonal Sparsifying Transform

How to learn an over complete dictionary for sparse representations of image is an important topic in machine learning, sparse coding, blind source separation, etc. The so-called K-singular value decomposition (K-SVD) method [3] is powerful for this purpose, however, it is too time-consuming to apply. Recently, an adaptive orthogonal sparsifying transform (AOST) method has been developed to learn the dictionary that is faster. However, the corresponding coefficient matrix may not be as sparse as that of K-SVD. For solving this problem, in this paper, a non-orthogonal iterative match method is proposed to learn the dictionary. By using the approach of sequentially extracting columns of the stacked image blocks, the non-orthogonal atoms of the dictionary are learned adaptively, and the resultant coefficient matrix is sparser. Experiment results show that the proposed method can yield effective dictionaries and the resulting image representation is sparser than AOST.

Nonnegative Matrix Factorization Applied to Nonlinear Speech and Image Cryptosystems

Nonnegative matrix factorization (NMF) is widely used in signal separation and image compression. Motivated by its successful applications, we propose a new cryptosystem based on NMF, where the nonlinear mixing (NLM) model with a strong noise is introduced for encryption and NMF is used for decryption. The security of the cryptosystem relies on following two facts: 1) the constructed multivariable nonlinear function is not invertible; 2) the process of NMF is unilateral, if the inverse matrix of the constructed linear mixing matrix is not nonnegative. Comparing with Lin's method (2006) that is a theoretical scheme using one-time padding in the cryptosystem, our cipher can be used repeatedly for the practical request, i.e., multitme padding is used in our cryptosystem. Also, there is no restriction on statistical characteristics of the ciphers and the plaintexts. Thus, more signals can be processed (successfully encrypted and decrypted), no matter they are correlative, sparse, or Gaussian. Furthermore, instead of the number of zero-crossing-based method that is often unstable in encryption and decryption, an improved method based on the kurtosis of the signals is introduced to solve permutation ambiguities in waveform reconstruction. Simulations are given to illustrate security and availability of our cryptosystem.

Nonnegative Blind Source Separation by Sparse Component Analysis Based on Determinant Measure

The problem of nonnegative blind source separation (NBSS) is addressed in this paper, where both the sources and the mixing matrix are nonnegative. Because many real-world signals are sparse, we deal with NBSS by sparse component analysis. First, a determinant-based sparseness measure, named D-measure, is introduced to gauge the temporal and spatial sparseness of signals. Based on this measure, a new NBSS model is derived, and an iterative sparseness maximization (ISM) approach is proposed to solve this model. In the ISM approach, the NBSS problem can be cast into row-to-row optimizations with respect to the unmixing matrix, and then the quadratic programming (QP) technique is used to optimize each row. Furthermore, we analyze the source identifiability and the computational complexity of the proposed ISM-QP method. The new method requires relatively weak conditions on the sources and the mixing matrix, has high computational efficiency, and is easy to implement. Simulation results demonstrate the effectiveness of our method.

Online blind source separation using incremental nonnegative matrix factorization with volume constraint

Online blind source separation (BSS) is proposed to overcome the high computational cost problem, which limits the practical applications of traditional batch BSS algorithms. However, the existing online BSS methods are mainly used to separate independent or uncorrelated sources. Recently, nonnegative matrix factorization (NMF) shows great potential to separate the correlative sources, where some constraints are often imposed to overcome the non-uniqueness of the factorization. In this paper, an incremental NMF with volume constraint is derived and utilized for solving online BSS. The volume constraint to the mixing matrix enhances the identifiability of the sources, while the incremental learning mode reduces the computational cost. The proposed method takes advantage of the natural gradient based multiplication updating rule, and it performs especially well in the recovery of dependent sources. Simulations in BSS for dual-energy X-ray images, online encrypted speech signals, and high correlative face images show the validity of the proposed method.