Homotopy Methods Based on $l_{0}$ -Norm for Compressed Sensing

A two-stage reconstruction method for complex networked system with hidden nodes

Reconstructing the interacting topology from measurable data is fundamental to understanding, controlling, and predicting the collective dynamics of complex networked systems. Many methods have been proposed to address the basic inverse problem and have achieved satisfactory performance. However, a significant challenge arises when we attempt to decode the underlying structure in the presence of inaccessible nodes due to the partial loss of information. For the purpose of improving the accuracy of network reconstruction with hidden nodes, we developed a robust two-stage network reconstruction method for complex networks with hidden nodes from a small amount of observed time series data. Specifically, the proposed method takes full advantage of the natural sparsity of complex networks and the potential symmetry constraints in dynamic interactions. With robust reconstruction, we can not only locate the position of hidden nodes but also precisely recover the overall network structure on the basis of compensated nodal information. Extensive experiments are conducted to validate the effectiveness of the proposed method and superiority compared with ordinary methods. To some extent, this work sheds light on addressing the inverse problem, of which the system lacks complete exploration in the network science community.

Robust multi-class feature selection via l2,0-norm regularization minimization

Feature selection is an important data preprocessing in data mining and machine learning, that can reduce the number of features without deteriorating model’s performance. Recently, sparse regression has received considerable attention in feature selection task due to its good performance. However, because the l2,0-norm regularization term is non-convex, this problem is hard to solve, and most of the existing methods relaxed it by l2,1-norm. Unlike the existing methods, this paper proposes a novel method to solve the l2,0-norm regularized least squares problem directly based on iterative hard thresholding, which can produce exact row-sparsity solution for weights matrix, and features can be selected more precisely. Furthermore, two homotopy strategies are derived to reduce the computational time of the optimization method, which are more practical for real-world applications. The proposed method is verified on eight biological datasets, experimental results show that our method can achieve higher classification accuracy with fewer number of selected features than the approximate convex counterparts and other state-of-the-art feature selection methods.

Fast Approximation for Sparse Coding with Applications to Object Recognition

Sparse Coding (SC) has been widely studied and shown its superiority in the fields of signal processing, statistics, and machine learning. However, due to the high computational cost of the optimization algorithms required to compute the sparse feature, the applicability of SC to real-time object recognition tasks is limited. Many deep neural networks have been constructed to low fast estimate the sparse feature with the help of a large number of training samples, which is not suitable for small-scale datasets. Therefore, this work presents a simple and efficient fast approximation method for SC, in which a special single-hidden-layer neural network (SLNNs) is constructed to perform the approximation task, and the optimal sparse features of training samples exactly computed by sparse coding algorithm are used as ground truth to train the SLNNs. After training, the proposed SLNNs can quickly estimate sparse features for testing samples. Ten benchmark data sets taken from UCI databases and two face image datasets are used for experiment, and the low root mean square error (RMSE) results between the approximated sparse features and the optimal ones have verified the approximation performance of this proposed method. Furthermore, the recognition results demonstrate that the proposed method can effectively reduce the computational time of testing process while maintaining the recognition performance, and outperforms several state-of-the-art fast approximation sparse coding methods, as well as the exact sparse coding algorithms.

Iterative Weighted Group Thresholding Method for Group Sparse Recovery

This article proposes a novel iterative weighted group thresholding method for group sparse recovery of signals from underdetermined linear systems. Based on an equivalent weighted group minimization problem with l_p^p -norm ( ), we derive closed-form solutions for a subproblem with respect to some specific values of p when using the proximal gradient method. Then, we design the corresponding algorithmic framework, including stopping criterion and the method of nonmonotone line search, and prove that the solution sequence generated by the proposed algorithm converges under some mild conditions. Moreover, based on the proposed algorithm, we develop a homotopy algorithm with an adaptively updated group threshold. Extensive computational experiments on the simulated and real data show that our approach is competitive with state-of-the-art methods in terms of exact group selection, estimation accuracy, and computation time.

Improved Generalized Sparsity Adaptive Matching Pursuit Algorithm Based on Compressive Sensing

The modified adaptive orthogonal matching pursuit algorithm has a lower convergence speed. To overcome this problem, an improved method with faster convergence speed is proposed. In respect of atomic selection, the proposed method computes the correlation between the measurement matrix and residual and then selects the atoms most related to residual to construct the candidate atomic set. The number of selected atoms is the integral multiple of initial step size. In respect of sparsity estimation, the proposed method introduces the exponential function to sparsity estimation. It uses a larger step size to estimate sparsity at the beginning of iteration to accelerate the algorithm convergence speed and a smaller step size to improve the reconstruction accuracy. Simulations show that the proposed method has better performance in terms of convergence speed and reconstruction accuracy for one-dimension signal and two-dimension signal.