This work aims to propose an approach for pruning a bagging ensemble regression (BER) model based on sparse representation, which we call sparse representation pruning (SRP). Firstly, a BER model with a specific number of subensembles should be trained. Then, the BER model is pruned by our sparse representation idea. For this type of regression problems, pruning means to remove the subensembles that do not have a significant effect on prediction of the output. The pruning problem is casted as a sparse representation problem, which will be solved by orthogonal matching pursuit (OMP) algorithm. Experiments show that the pruned BER with only 20% of the initial subensembles has a better generalization compared to a complete BER.

In dictionary learning, a desirable property for the dictionary is to be of low mutual and average coherences. Mutual coherence is defined as the maximum absolute correlation between distinct atoms of the dictionary, whereas the average coherence is a measure of the average correlations. In this paper, we consider a dictionary learning problem regularized with the average coherence and constrained by an upper-bound on the mutual coherence of the dictionary. Our main contribution is then to propose an algorithm for solving the resulting problem based on convexly approximating the cost function over the dictionary. Experimental results demonstrate that the proposed approach has higher convergence rate and lower representation error (with a fixed sparsity parameter) than other methods, while yielding similar mutual and average coherence values.

In graph signal processing (GSP), graph learning is concerned with the inference of an underlying graph best capable of modeling a dataset of graph signals. However, more complex datasets are derived from multiple underlying graphs. In such instances, it is necessary to learn multiple graph structures, each corresponding to the graph signals residing on the same structure. In other words, the graph signals need to be partitioned into a set of clusters, with a designated topology for each cluster. In this letter, inspired from classical K-means, a new algorithm for multiple graph learning, called K-graphs, is proposed. Numerical experiments demonstrate the high performance of this algorithm, in both graph learning and data clustering.

In this paper, a proof is provided to show that Gaussian signals will lose their Gaussianity if they are passed through a polynomial of an order greater than 1. This can help in blind compensation of polynomial nonlinearities on Gaussian sources by forcing the output to follow a Gaussian distribution (the term “blind” refers to lack of any prior information about the nonlinear function). It may have many applications in different fields of nonlinear signal processing for removing the nonlinearity. Particularly, in nonlinear blind source separation, it can be used as a pre-processing step to transform the problem to a linear one, which is already well studied in the literature. This idea is proposed, proved, and finally verified by a simple simulation as a proof of concept in this paper.

Hyperspectral image unmixing is a source separation problem whose goal is to identify the signatures of the materials present in the imaged scene (called endmembers), and to estimate their proportions (called abundances) in each pixel. Usually, the contributions of each material are assumed to be perfectly represented by a single spectral signature and to add up in a linear way. However, the main two limitations of this model have been identified as nonlinear mixing phenomena and spectral variability, i.e., the intraclass variability of the materials. The former limitation has been addressed by designing nonlinear mixture models, whereas the second can be dealt with by using (usually linear) space varying models. The typical example is a linear mixing model where the sources can vary from one pixel to the other. In this letter, we show that a recent variability model can also estimate the abundances of nonlinear mixtures to some extent. We make the theoretical connection between nonlinear models and this variability model, and confirm it with experiments on nonlinearly generated synthetic datasets.

This letter is concerned with designing incoherent unit-norm frames, i.e., a set of vectors in a finite dimensional Hilbert space with unit norms and very low absolute pairwise correlations. Due to their widespread use in a variety of applications, including compressed sensing and coding theory, incoherent frame design has received considerable attention, and many algorithms have been proposed to this aim. In this letter, a new algorithm is presented which constructs incoherent frames by minimizing the maximum absolute pairwise correlations (mutual coherence) of the frame vectors. Our strategy is based on an alternating minimization penalty method, which admits efficient solvers using proximal algorithms. Experimental results on designing incoherent frames of various dimensions show that our algorithm outperforms some recent methods in the literature.

In this paper, a property for sparse recovery algorithms, called invariancy, is introduced. The significance of invariancy is that the performance of the algorithms with this property is less affected when the sensing (i.e., the dictionary) is ill-conditioned. This is because for this kind of algorithms, there exists implicitly an equivalent well-conditioned problem, which is being solved. Some examples of sparse recovery algorithms will also be considered and it will be shown that some of them, such as SL0, Basis Pursuit (using interior point LP solver), FOCUSS, and hard thresholding algorithms, are invariant, and some others, like Matching Pursuit and SPGL1, are not. Then, as an application example of the invariancy property, a sparse-decomposition-based method for direction of arrival estimation is reviewed, and it is shown that if an invariant algorithm is utilized for solving the corresponding sparse recovery problem, the spatial characteristics of the sensors will have essentially no effect on the final estimation, provided that the number of sensors is large enough.

In this paper we address the problem of image interpolation using Gaussian Mixture Models (GMM) as a prior. Previous methods of image restoration with GMM have not considered spatial (geometric) distance between patches in clustering, failing to fully exploit the coherency of nearby patches. The GMM framework in our method for image interpolation is based on the assumption that the accumulation of similar patches in a neighborhood are derived from a multivariate Gaussian probability distribution with a specific covariance and mean. An Expectation Maximization-like (EM-like) algorithm is used in order to determine patches in a cluster and restore them. The results show that our image interpolation method outperforms previous state-of-the-art methods with an acceptable bound.

In this paper, we address the problem of recovering degraded images using multivariate Gaussian mixture model (GMM) as a prior. The GMM framework in our method for image restoration is based on the assumption that the accumulation of similar patches in a neighborhood are derived from a multivariate Gaussian probability distribution with a specific covariance and mean. Previous methods of image restoration with GMM have not considered spatial (geometric) distance between patches in clustering. Our conducted experiments show that in the case of constraining Gaussian estimates into a finite-sized windows, the patch clusters are more likely to be derived from the estimated multivariate Gaussian distributions, i.e., the proposed statistical patch-based model provides a better goodness-of-fit to statistical properties of natural images. A novel approach for computing aggregation weights for image reconstruction from recovered patches is introduced which is based on similarity degree of each patch to the estimated Gaussian clusters. The results admit that in the case of image denoising, our method is highly comparable with the state-of-the-art methods, and our image interpolation method outperforms previous state-of-the-art methods.

During the last decade, there has been a growing interest toward the problem of sparse decomposition. A very important task in this field is dictionary learning, which is designing a suitable dictionary that can sparsely represent a group of training signals. In most dictionary learning algorithms, the cost function to determine the the optimum dictionary is the ℓ0norm of the matrix of decomposition coefficients of the training signals. However, we believe that this cost function fails to fully express the goal of dictionary learning, because it only sparsifies the whole set of coefficients for all training signals, rather than the coefficients for each training signal individually. Thus, in this paper we present a new criterion for dictionary learning. We then propose a new dictionary learning algorithm that solves our proposed optimization problem for the case of complete dictionaries. The proposed algorithm follows the idea of smoothed ℓ0(SL0) algorithm for sparse recovery. Simulation results emphasize the efficiency of the proposed cost function and algorithm.

A dictionary learning problem is a matrix factorization in which the goal is to factorize a training data matrix, Y, as the product of a dictionary, D, and a sparse coefficient matrix, X, as follows, Y ≃ DX. Current dictionary learning algorithms minimize the representation error subject to a constraint on D (usually having unit column-norms) and sparseness of X. The resulting problem is not convex with respect to the pair (D,X). In this letter, we derive a first order series expansion formula for the factorization, DX. The resulting objective function is jointly convex with respect to D and X. We simply solve the resulting problem using alternating minimization and apply some of the previously suggested algorithms onto our new problem. Simulation results on recovery of a known dictionary and dictionary learning for natural image patches show that our new problem considerably improves performance with a little additional computational load.

Standard sparse decomposition (with applications in many different areas including compressive sampling) amounts to finding the minimum ℓ0-norm solution of an underdetermined system of linear equations. In this decomposition, all atoms are treated `uniformly' for being included or not in the decomposition. However, one may wish to weigh more or less certain atoms, or, assign higher costs to some other atoms to be included in the decomposition. This can happen for example when there is prior information available on each atom. This motivates generalizing the notion of minimal ℓ0-norm solution to that of minimal weighted ℓ0-norm solution. On the other hand, relaxing weighted ℓ0-norm via the weighted ℓ1-norm is challenging. This paper deals with minimal weighted ℓ0-norm solutions of underdetermined linear systems, provides conditions for their uniqueness, and develops an algorithm for their estimation.

In this paper, we address the matrix completion problem and propose a novel algorithm based on a smoothed rank function (SRF) approximation. Among available algorithms like FPCA and OptSpace, there is no solution that can simultaneously cover wide range of easy and hard problems. This new algorithm provides accurate results in almost all scenarios with a reasonable run time. It especially has low execution time in hard problems where other methods need long time to converge. Furthermore, when the rank is known in advance and is high, our method is very faster than previous methods for the same accuracy. The main idea of the algorithm is based on a continuous and differentiable approximation of the rank function and then, using gradient projection approach to minimize it.

Let${\bf A}$be an$n \times m$matrix with$m > n$, and suppose that the underdetermined linear system${\bf A} {\bf s} = {\bf x}$admits a sparse solution${\bf s}_0$for which$\Vert {\bf s}_0\Vert_0 < {1\over 2} {\rm spark}({\bf A})$. Such a sparse solution is unique due to a well-known uniqueness theorem. Suppose now that we have somehow a solution$\mathhat{\bf s}$as an estimation of${\bf s}_0$, and suppose that$\mathhat{\bf s}$is only “approximately sparse,” that is, many of its components are very small and nearly zero, but not mathematically equal to zero. Is such a solution necessarily close to the true sparsest solution? More generally, is it possible to construct an upper bound on the estimation error$\Vert \mathhat{\bf s}-{\bf s}_0\Vert_2$without knowing${\bf s}_0$? The answer is positive, and in this paper, we construct such a bound based on minimal singular values of submatrices of${\bf A}$. We will also state a tight bound, which is more complicated, but besides being tight, enables us to study the case of random dictionaries and obtain probabilistic upper bounds. We will also study the noisy case, that is, where${\bf x} = {\bf A} {\bf s}+{\bf n}$. Moreover, we will see that where$\Vert{{\bf s}_0}\Vert_0$grows, to obtain a predetermined guaranty on the maximum of$\Vert{\mathhat{\bf s}-{\bf s}_0}\Vert_2,$$\mathhat{\bf s}$is needed to be sparse with a better approximation. This can be seen as an explanation to the fact that the estimation quality of sparse recovery algorithms degrades where$\Vert{{\bf s}_0}\Vert_0$grows.

Independent Component Analysis (ICA) can be used to decompose functional Magnetic Resonance Imaging (fMRI) data into a set of statistically independent images which are likely to be the sources of fMRI data. After applying ICA, a set of independent components are produced, and then, a “meaningful” subset from these components must be identified, because a large majority of components are non-interesting. So, interpreting the components is an important and also difficult task. In this paper, we propose a criterion based on the entropy of time courses to automatically select the components of interest. This method does not require to know the stimulus pattern of the experiment.

In this paper, we suggest to use a steepest descent algorithm for learning a parametric dictionary in which the structure or atom functions are known in advance. The structure of the atoms allows us to find a steepest descent direction of parameters instead of the steepest descent direction of the dictionary itself. We also use a thresholded version of Smoothed-ℓ0(SL0) algorithm for sparse representation step in our proposed method. Our simulation results show that using atom structure similar to the Gabor functions and learning the parameters of these Gabor-like atoms yield better representations of our noisy speech signal than non parametric dictionary learning methods like K-SVD, in terms of mean square error of sparse representations.

Sparse Decomposition (SD) of a signal on an overcomplete dictionary has recently attracted a lot of interest in signal processing and statistics, because of its potential application in many different areas including Compressive Sensing (CS). However, in the current literature, the dictionary matrix has generally been assumed to be of full-rank. In this paper, we consider non-full-rank dictionaries (which are not even necessarily overcomplete), and extend the definition of SD over these dictionaries. Moreover, we present an approach which enables to use previously developed SD algorithms for this non-full-rank case. Besides this general approach, for the special case of the Smoothed ℓ0(SL0) algorithm, we show that a slight modification of it covers automatically non-full-rank dictionaries.

In the last few years, we have witnessed an explosion in applications of sparse representation, the majority of which share the need for finding sparse solutions of underdetermined systems of linear equations (USLE's). Based on recently proposed smoothed lscr0-norm (SL0), we develop a noise-tolerant algorithm for sparse representation, namely Robust-SL0, enjoying the same computational advantages of SL0, while demonstrating remarkable robustness against noise. The proposed algorithm is developed by adopting the corresponding optimization problem for noisy settings, followed by theoretically-justified approximation to reduce the complexity. Stability properties of robust-SL0 are rigorously analyzed, both analytically and experimentally, revealing a remarkable improvement in performance over SL0 and other competing algorithms, in the presence of noise.

In this paper, we consider sparse decomposition (SD) of two-dimensional (2D) signals on overcomplete dictionaries with separable atoms. Although, this problem can be solved by converting it to the SD of one-dimensional (1D) signals, this approach requires a tremendous amount of memory and computational cost. Moreover, the uniqueness constraint obtained by this approach is too restricted. Then in the paper, we present an algorithm to be used directly for sparse decomposition of 2D signals on dictionaries with separable atoms. Moreover, we will state another uniqueness constraint for this class of decomposition. Our algorithm is obtained by modifying the Smoothed L0 (SL0) algorithm, and hence we call it two-dimensional SL0 (2D-SL0).

Recently, a lot of research has been done on compressed sensing, capturing compressible signals using random linear projections to a space of radically lower dimension than the ambient dimension of the signal. The main impetus of this is that the radically dimension-lowering linear projection step can be done totally in analog hardware, in some cases even in constant time, to avoid the bottleneck in sensing and quantization steps where a large number of samples need to be sensed and quantized in short order, mandating the use of a large number of fast expensive sensors and A/D converters. Reconstruction algorithms from these projections have been found that come within distortion levels comparable to the state of the art in lossy compression algorithms. This paper considers a variation on compressed sensing that makes it resistant to spiky noise. This is achieved by an analog real-field error-correction coding step. It results in a small asymptotic overhead in the number of samples, but makes exact reconstruction under spiky measurement noise, one type of which is the salt and pepper noise in imaging devices, possible. Simulations are performed that corroborate our claim and in fact substantially improve reconstruction under unreliable sensing characteristics and are stable even under small perturbations with Gaussian noise.

In this paper, we suggest to use a modified version of Smoothed-lscr0(SL0) algorithm in the sparse representation step of iterative dictionary learning algorithms. In addition, we use a steepest descent for updating the non unit column-norm dictionary instead of unit column-norm dictionary. Moreover, to do the dictionary learning task more blindly, we estimate the average number of active atoms in the sparse representation of the training signals, while previous algorithms assumed that it is known in advance. Our simulation results show the advantages of our method over K-SVD in terms of complexity and performance.

In this paper, we propose a Bayesian pursuit algorithm for sparse representation. It uses both the simplicity of the pursuit algorithms and optimal Bayesian framework to determine active atoms in sparse representation of a signal. We show that using Bayesian Hypothesis testing to determine the active atoms from the correlations leads to an efficient activity measure. Simulation results show that our suggested algorithm has better performance among the algorithms which have been implemented in our simulations in most of the cases.

The theory of compressive sampling involves making random linear projections of a signal. Provided signal is sparse in some basis, small number of such measurements preserves the information in the signal, with high probability. Following the success in signal reconstruction, compressive framework has recently proved useful in classification. In this paper, conventional random projection scheme is first extended to the image domain and the key notion of concentration of measure is studied. Findings are then employed to develop a 2D compressive classifier (2D-CC) for sparse images. Finally, theoretical results are validated within a realistic experimental framework.

In this paper an extension of the sparse decomposition problem is considered and an algorithm for solving it is presented. In this extension, it is known that one of the shifted versions of a signal s (not necessarily the original signal itself) has a sparse representation on an overcomplete dictionary, and we are looking for the sparsest representation among the representations of all the shifted versions of s. Then, the proposed algorithm finds simultaneously the amount of the required shift, and the sparse representation. Experimental results emphasize on the performance of our algorithm.

In this paper we present an algorithm for complex-valued sparse representation. In our previous work we presented an algorithm for sparse representation based on smoothed lscrdeg- norm. Here we extend that algorithm to complex-valued signals. The proposed algorithm is compared to FOCUSS algorithm and it is experimentally shown that the proposed algorithm is about two or three orders of magnitude faster than FOCUSS while providing approximately the same accuracy.

In this paper, a new approach for decoding real-field codes based on finding sparse solutions of underdetermined linear systems is proposed. This algorithm iteratively estimates the positions and the amplitudes of the sparse errors (or noise impulses) using an expectation-maximization (EM) algorithm. Iterative estimation of amplitudes is done in the expectation step (E-step), while iterative estimation of error positions is done in the maximization step (M-step). Simulation results show 1-2 dB improvement over linear programming (LP) which has been previously used for error correction.

In this letter, we address the theoretical limitations in estimating the mixing matrix in noisy sparse component analysis (SCA) for the two-sensor case. We obtain the Cramer-Rao lower bound (CRLB) error estimation of the mixing matrix. Using the Bernouli-Gaussian (BG) sparse distribution, and some simple assumptions, an approximation of the Fisher information matrix (FIM) is calculated. Moreover, this CRLB is compared to some of the main methods of mixing matrix estimation in the literature.

A new algorithm for blind source separation in convolutive mixtures, based on minimizing the mutual information of the outputs, is proposed. This minimization is done using a recently proposed minimization-projection (MP) approach for minimizing mutual information in a parametric model. Since the minimization step of the MP approach is proved to have no local minimum, it is expected that this new algorithm has good convergence behaviour.

In this letter, we compute the variation of the mutual information, resulting from a small variation in its argument. Although the result can be applied in many problems, we consider only one example: the result is used for deriving a new method for blind source separation in linear mixtures. The experimental results emphasize the performance of the resulting algorithm.