In this paper, we propose L0 norm optimization in a scrambled sparse representation domain and its application to an Encryption-then-Compression (EtC) system. We design a random unitary transform that conserves L0 norm isometry. The resulting encryption method provides a practical orthogonal matching pursuit (OMP) algorithm that allows computation in the encrypted domain. We prove that the proposed method theoretically has exactly the same estimation performance as the nonencrypted variant of the OMP algorithm. In addition, we demonstrate the security strength of the proposed secure sparse representation when applied to the EtC system. Even if the dictionary information is leaked, the proposed scheme protects the privacy information of observed signals.

In this paper, we propose a secure computation of sparse coding and its application to Encryption-then-Compression (EtC) systems. The proposed scheme introduces secure sparse coding that allows computation of an Orthogonal Matching Pursuit (OMP) algorithm in an encrypted domain. We prove theoretically that the proposed method estimates exactly the same sparse representations that the OMP algorithm for non-encrypted computation does. This means that there is no degradation of the sparse representation performance. Furthermore, the proposed method can control the sparsity without decoding the encrypted signals. Next, we propose an EtC system based on the secure sparse coding. The proposed secure EtC system can protect the private information of the original image contents while performing image compression. It provides the same rate-distortion performance as that of sparse coding without encryption, as demonstrated on both synthetic data and natural images.

Parameter estimation theorems for LFM signals have been developed due to the advantages of fractional Fourier transform (FrFT). The traditional estimation methods in the fractional Fourier domain (FrFD) are almost based on two-dimensional search which have the contradiction between estimation performance and complexity. In order to solve this problem, we introduce the orthogonal matching pursuit (OMP) into the FrFD, propose a modified optimization method to estimate initial frequency and final frequency of fractional bandlimited LFM signals. In this algorithm, the differentiation fractional spectrum which is used to form observation matrix in OMP is derived from the spectrum analytical formulations of the LFM signal, and then, based on that the LFM signal has approximate rectangular spectrum in the FrFD and the correlation between the LFM signal and observation matrix yields a maximal value at the edge of the spectrum (see Sect.3.3 for details), the edge spectrum information can be extracted by OMP. Finally, the estimations of initial frequency and final frequency are obtained through multiplying the edge information by the sampling frequency resolution. The proposed method avoids reconstruction and the traditional peak-searching procedure, and the iterations are needed only twice. Thus, the computational complexity is much lower than that of the existing methods. Meanwhile, Since the vectors at the initial frequency and final frequency points both have larger modulus, so that the estimations are closer to the actual values, better normalized root mean squared error (NRMSE) performance can be achieved. Both theoretical analysis and simulation results demonstrate that the proposed algorithm bears a relatively low complexity and its estimation precision is higher than search-based and reconstruction-based algorithms.

In this letter, we propose a generalized quadrature spatial modulation technique (GQSM) which offers additional bits per channel use (bpcu) gains and a low complexity greedy detector algorithm, structured orthogonal matching pursuit (S-OMP)- GQSM, based on compressive sensing (CS) framework. Simulation results show that the bit error rate (BER) performance of the proposed greedy detector is very close to maximum likelihood (ML) and near optimal detectors based on convex programming.

Mutipath matching pursuit (MMP) is a new reconstruction algorithm based on compressed sensing (CS). In this letter, we applied the MMP algorithm to channel estimation in orthogonal frequency division multiplexing (OFDM) communication systems, and then proposed an improved MMP algorithm. The improved method adjusted the number of children generated by candidates. It can greatly reduce the complexity. The simulation results demonstrate that the improved method can reduce the running time under the premise of guaranteeing the performance of channel estimation.

This paper proposes a novel matching pursuit generalized approximate message passing (MPGAMP) algorithm which explores the support of sparse representation coefficients step by step, and estimates the mean and variance of non-zero elements at each step based on a generalized-approximate-message-passing-like scheme. In contrast to the classic message passing based algorithms and matching pursuit based algorithms, our proposed algorithm saves a lot of intermediate process memory, and does not calculate the inverse matrix. Numerical experiments show that MPGAMP algorithm can recover a sparse signal from compressed sensing measurements very well, and maintain good performance even for non-zero mean projection matrix and strong correlated projection matrix.

A signal-model-based SAR image formation algorithm is proposed in this paper. A model is used to describe the received signal, and each scatterer can be characterized by a set of its parameters. Two parameter estimation methods via atomic decomposition are presented: (1) applying 1-D matching pursuit to azimuthal projection data; (2) applying 2-D matching pursuit to raw data. The estimated parameters are mapped to form a SAR image, and the mapping procedure can be implemented under application guidelines. This algorithm requires no prior information about the relative motion between the platform and the target. The Cramer-Rao bounds of parameter estimation are derived, and the root mean square errors of the estimates are close to the bounds. Experimental results are given to validate the algorithm and indicate its potential applications.

This paper proposes a novel greedy algorithm, called Creditability-Estimation based Matching Pursuit (CEMP), for the compressed sensing signal recovery. As proved in the algorithm of Stagewise Orthogonal Matching Pursuit (StOMP), two Gaussian distributions are followed by the matched filter coefficients corresponding to and without corresponding to the actual support set of the original sparse signal, respectively. Therefore, the selection for each support point is interpreted as a process of hypothesis testing, and the preliminarily selected support set is supposed to consist of rejected atoms. A hard threshold, which is controlled by an input parameter, is used to implement the rejection. Because the Type I error may happen during the hypothesis testing, not all the rejected atoms are creditable to be the true support points. The creditability of each preliminarily selected support point is evaluated by a well-designed built-in mechanism, and the several most creditable ones are adaptively selected into the final support set without being controlled by any extra external parameters. Moreover, the proposed CEMP does not necessitate the sparsity level to be a priori control parameter in operation. In order to verify the performance of the proposed algorithm, Gaussian and Pulse Amplitude Modulation sparse signals are measured in the noiseless and noisy cases, and the experiments of the compressed sensing signal recoveries by several greedy algorithms including CEMP are implemented. The simulation results show the proposed CEMP can achieve the best performances of the recovery accuracy and robustness as a whole. Besides, the experiment of the compressed sensing image recovery shows that CEMP can recover the image with the highest Peak Signal to Noise Ratio (PSNR) and the best visual quality.

There have been many matching pursuit algorithms (MPAs) which handle the sparse signal recovery problem, called compressed sensing (CS). In the MPAs, the correlation step makes a dominant computational complexity. In this paper, we propose a new fast correlation method for the MPA when we use partial Fourier sensing matrices and partial Hadamard sensing matrices which are widely used as the sensing matrix in CS. The proposed correlation method can be applied to almost all MPAs without causing any degradation of their recovery performance. Also, the proposed correlation method can reduce the computational complexity of the MPAs well even though there are restrictions depending on a used MPA and parameters.

We propose a variant of OMP algorithm named BROMP for sparse solution. In our algorithm, the update rule of MP algorithm is employed to reduce the number of least square calculations and the refining strategy is introduced to further improve its performance. Simulations show that the proposed algorithm performs better than the OMP algorithm with significantly lower complexity.

In this letter, parallel orthogonal matching pursuit (POMP) is proposed to supplement orthogonal matching pursuit (OMP) which has been widely used as a greedy algorithm for sparse signal recovery. Empirical simulations show that POMP outperforms the existing sparse signal recovery algorithms including OMP, compressive sampling matching pursuit (CoSaMP), and linear programming (LP) in terms of the exact recovery ratio (ERR) for the sparse pattern and the mean-squared error (MSE) between the estimated signal and the original signal.

In this paper, a novel algorithm, Cross Low-dimension Pursuit, based on a new structured sparse matrix, Permuted Block Diagonal (PBD) matrix, is proposed in order to recover sparse signals from incomplete linear measurements. The main idea of the proposed method is using the PBD matrix to convert a high-dimension sparse recovery problem into two (or more) groups of highly low-dimension problems and crossly recover the entries of the original signal from them in an iterative way. By sampling a sufficiently sparse signal with a PBD matrix, the proposed algorithm can recover it efficiently. It has the following advantages over conventional algorithms: (1) low complexity, i.e., the algorithm has linear complexity, which is much lower than that of existing algorithms including greedy algorithms such as Orthogonal Matching Pursuit and (2) high recovery ability, i.e., the proposed algorithm can recover much less sparse signals than even 1-norm minimization algorithms. Moreover, we demonstrate both theoretically and empirically that the proposed algorithm can reliably recover a sparse signal from highly incomplete measurements.

Multipath is one of the major error sources that deteriorates tracking performance in global navigation satellite system (GNSS). In this letter, the orthogonal matching pursuit (OMP) algorithm is used to estimate multipaths which are highly correlated with the line of signal (LoS) signal. The estimated multipaths are subtracted from the received signal such that the autocorrelation function of the received signal is restored to optimize the tracking performance. The performance of the proposed technique is verified via computer simulations under the multipath environment of GNSS.

A method for reducing ground clutter contribution from ground penetrating radar (GPR) data is proposed for discrimination of landmines located in shallow depth. The algorithm of this method is based on the Matching Pursuit (MP) that is a technique for non-orthogonal signal decomposition using dictionary of functions. As the dictionary of function, a wave-based dictionary constructed by taking account of scattering mechanisms of electromagnetic (EM) wave by rough surfaces is employed. Through numerical simulations, performance of ground clutter reduction is evaluated. The results show that the proposed method has good performance and is effective for GPR data preprocessing for discrimination of shallowly buried landmines.

The GNSS receivers suffer from the multipath interference which is highly correlated with the line of sight (LoS) signal. Such interference results in tracking and ranging errors. In this paper, we propose a novel algorithm that can estimate the direction of arrival (DoA) of the LoS signal in the presence of highly correlated multipath interference. The proposed algorithm combines the matching pursuits algorithm for multipath estimation and the minimum norm algorithm for DoA estimation. An efficient combination of two algorithms yields reliable estimates of the DoA of LoS signal as demonstrated by computer simulations.

A new sinusoidal modeling approach for the analysis-by-synthesis (AbS) of parameters that characterize a linear combination of damped sinusoids is proposed. In addition to the typical sinusoidal parameters, two different damping factors, which represent the time-varying nature of speech, were used to efficiently reduce the modeling error. Even though the proposed model does not employ the overlap-adding synthesis or smoothly interpolative synthesis scheme, it shows substantially better modeling performance in the synthesis of voiced and transient segments.

Matching Pursuits (MP), a technique for signal decomposition using a dictionary of functions, is applied to ground penetrating radar (GPR) signals in order to remove noise and clutter included in the signals and to extract target responses. A wave-based dictionary composed of wavefronts and resonances is employed. Noise reduction performance and the removal of ground-surface reflection are evaluated through numerical simulations. The results show that the MP approach performs well and offers an effective method for feature extraction from GPR signals.

In this paper, we propose an ECG waveform compression technique based on the matching pursuit. The matching pursuit is an iterative non-orthogonal signal expansion technique. A signal is decomposed to atoms in a function dictionary. The constraint to the dictionary is only the over-completeness to signals. The function dictionary can be defined to be best match to the structure of the ECG waveform. In this paper, we introduce the multiscale analysis to the implementation of inner product computations between signals and atoms in the matching pursuit iteration. The computational cost can be reduced by utilization of the filter bank of the multiscale analysis. We show the waveform approximation capability of the matching pursuit with multiscale analysis. We show that a simple 4-tap integer filter bank is enough to the approximation and compression of ECG waveforms. In ECG waveform compression, we apply the error feed-back procedure to the matching pursuit iteration to reduce the norm of the approximation error. Finally, actual ECG waveform compression by the proposed method are demonstrated. The proposed method achieve the compression by the factor 10 to 30. The compression ratio given by the proposed method is higher than the orthogonal wavelet transform coding in the range of the reconstruction precision lower than 9% in PRD.

Matching pursuit is a signal expansion technique whose efficiency for motion compensated residual image has been successfully demonstrated in the MPEG-4 development. However, one of the practical concerns related to applying matching pursuit algorithm to real-time coding of video is its massive computation required for finding atoms. This paper proposes a new fast method based on three properties of basis functions used in the signal expansion. The first one is the symmetry property of the 1-D bases. The second one is that one can preclude many bases that cannot be atom by checking a simple mathematical condition. The last one is the classification property of 2-D bases in a given dictionary. Experimental result shows that our method can perform the same matching pursuit without any image degradation using only about 40% of computational load required by the conventional fast method based on separability of 2-D Gabor dictionary. Furthermore, if negligible quality degradation is allowed, the method can be extended to perform matching pursuit with only about 10% of the computational load required by the conventional fast method. We apply the proposed fast matching pursuit method to scalable coding of video with two layers.