Given that the concurrent L1-minimization(L1-min)problem is often required in some real applications,we investigate how to solve it in parallel on GPUs in this paper.First,we propose a novel self-adaptive warp impleme...Given that the concurrent L1-minimization(L1-min)problem is often required in some real applications,we investigate how to solve it in parallel on GPUs in this paper.First,we propose a novel self-adaptive warp implementation of the matrix-vector multiplication(Ax)and a novel self-adaptive thread implementation of the matrix-vector multiplication(ATx),respectively,on the GPU.The vector-operation and inner-product decision trees are adopted to choose the optimal vector-operation and inner-product kernels for vectors of any size.Second,based on the above proposed kernels,the iterative shrinkage-thresholding algorithm is utilized to present two concurrent L1-min solvers from the perspective of the streams and the thread blocks on a GPU,and optimize their performance by using the new features of GPU such as the shuffle instruction and the read-only data cache.Finally,we design a concurrent L1-min solver on multiple GPUs.The experimental results have validated the high effectiveness and good performance of our proposed methods.展开更多
For indoor location estimation based on received signal strength( RSS) in wireless local area networks( WLAN),in order to reduce the influence of noise on the positioning accuracy,a large number of RSS should be colle...For indoor location estimation based on received signal strength( RSS) in wireless local area networks( WLAN),in order to reduce the influence of noise on the positioning accuracy,a large number of RSS should be collected in offline phase. Therefore,collecting training data with positioning information is time consuming which becomes the bottleneck of WLAN indoor localization. In this paper,the traditional semisupervised learning method based on k-NN and ε-NN graph for reducing collection workload of offline phase are analyzed,and the result shows that the k-NN or ε-NN graph are sensitive to data noise,which limit the performance of semi-supervised learning WLAN indoor localization system. Aiming at the above problem,it proposes a l1-graph-algorithm-based semi-supervised learning( LG-SSL) indoor localization method in which the graph is built by l1-norm algorithm. In our system,it firstly labels the unlabeled data using LG-SSL and labeled data to build the Radio Map in offline training phase,and then uses LG-SSL to estimate user's location in online phase. Extensive experimental results show that,benefit from the robustness to noise and sparsity ofl1-graph,LG-SSL exhibits superior performance by effectively reducing the collection workload in offline phase and improving localization accuracy in online phase.展开更多
The generalized l1 greedy algorithm was recently introduced and used to reconstruct medical images in computerized tomography in the compressed sensing framework via total variation minimization. Experimental results ...The generalized l1 greedy algorithm was recently introduced and used to reconstruct medical images in computerized tomography in the compressed sensing framework via total variation minimization. Experimental results showed that this algorithm is superior to the reweighted l1-minimization and l1 greedy algorithms in reconstructing these medical images. In this paper the effectiveness of the generalized l1 greedy algorithm in finding random sparse signals from underdetermined linear systems is investigated. A series of numerical experiments demonstrate that the generalized l1 greedy algorithm is superior to the reweighted l1-minimization and l1 greedy algorithms in the successful recovery of randomly generated Gaussian sparse signals from data generated by Gaussian random matrices. In particular, the generalized l1 greedy algorithm performs extraordinarily well in recovering random sparse signals with nonzero small entries. The stability of the generalized l1 greedy algorithm with respect to its parameters and the impact of noise on the recovery of Gaussian sparse signals are also studied.展开更多
The guidance and control for UAV aerial refueling docking based on dynamic inversion with L1 adaptive augmentation is studied.In order to improve the tracking performance of UAV aerial refueling docking,aguidance algo...The guidance and control for UAV aerial refueling docking based on dynamic inversion with L1 adaptive augmentation is studied.In order to improve the tracking performance of UAV aerial refueling docking,aguidance algorithm is developed to satisfy the tracking requirement of position and velocity,and it generates the UAV flight control loop commands.In flight control loop,based on the 6-DOF nonlinear model,the angular rate loop and the attitude loop are separated based on time-scale principle and the control law is designed using dynamic inversion.The throttle control is also derived from dynamic inversion method.Moreover,an L1 adaptive augmentation is developed to compensate for the undesirable effects of modeling uncertainty and disturbance.Nonlinear digital simulations are carried out.The results show that the guidance and control system has good tracking performance and robustness in achieving accurate aerial refueling docking.展开更多
With the help of the asymptotic expansion for the classic Li formula and based on the L1-type compact difference scheme,we propose a temporal Richardson extrapolation method for the fractional sub-diffusion equation.T...With the help of the asymptotic expansion for the classic Li formula and based on the L1-type compact difference scheme,we propose a temporal Richardson extrapolation method for the fractional sub-diffusion equation.Three extrapolation formulas are presented,whose temporal convergence orders in L_(∞)-norm are proved to be 2,3-α,and 4-2α,respectively,where 0<α<1.Similarly,by the method of order reduction,an extrapola-tion method is constructed for the fractional wave equation including two extrapolation formulas,which achieve temporal 4-γ and 6-2γ order in L_(∞)-norm,respectively,where1<γ<2.Combining the derived extrapolation methods with the fast algorithm for Caputo fractional derivative based on the sum-of-exponential approximation,the fast extrapolation methods are obtained which reduce the computational complexity significantly while keep-ing the accuracy.Several numerical experiments confirm the theoretical results.展开更多
Compressive sensing(CS)is an emerging methodology in computational signal processing that has recently attracted intensive research activities.At present,the basic CS theory includes recoverability and stability:the f...Compressive sensing(CS)is an emerging methodology in computational signal processing that has recently attracted intensive research activities.At present,the basic CS theory includes recoverability and stability:the former quantifies the central fact that a sparse signal of length n can be exactly recovered from far fewer than n measurements via l1-minimization or other recovery techniques,while the latter specifies the stability of a recovery technique in the presence of measurement errors and inexact sparsity.So far,most analyses in CS rely heavily on the Restricted Isometry Property(RIP)for matrices.In this paper,we present an alternative,non-RIP analysis for CS via l1-minimization.Our purpose is three-fold:(a)to introduce an elementary and RIP-free treatment of the basic CS theory;(b)to extend the current recoverability and stability results so that prior knowledge can be utilized to enhance recovery via l1-minimization;and(c)to substantiate a property called uniform recoverability of l1-minimization;that is,for almost all random measurement matrices recoverability is asymptotically identical.With the aid of two classic results,the non-RIP approach enables us to quickly derive from scratch all basic results for the extended theory.展开更多
In this paper, we consider an extragradient thresholding algorithm for finding the sparse solution of mixed complementarity problems (MCPs). We establish a relaxation l1 regularized projection minimization model for t...In this paper, we consider an extragradient thresholding algorithm for finding the sparse solution of mixed complementarity problems (MCPs). We establish a relaxation l1 regularized projection minimization model for the original problem and design an extragradient thresholding algorithm (ETA) to solve the regularized model. Furthermore, we prove that any cluster point of the sequence generated by ETA is a solution of MCP. Finally, numerical experiments show that the ETA algorithm can effectively solve the l1 regularized projection minimization model and obtain the sparse solution of the mixed complementarity problem.展开更多
基金The research has been supported by the Natural Science Foundation of China under great number 61872422the Natural Science Foundation of Zhejiang Province,China under great number LY19F020028.
文摘Given that the concurrent L1-minimization(L1-min)problem is often required in some real applications,we investigate how to solve it in parallel on GPUs in this paper.First,we propose a novel self-adaptive warp implementation of the matrix-vector multiplication(Ax)and a novel self-adaptive thread implementation of the matrix-vector multiplication(ATx),respectively,on the GPU.The vector-operation and inner-product decision trees are adopted to choose the optimal vector-operation and inner-product kernels for vectors of any size.Second,based on the above proposed kernels,the iterative shrinkage-thresholding algorithm is utilized to present two concurrent L1-min solvers from the perspective of the streams and the thread blocks on a GPU,and optimize their performance by using the new features of GPU such as the shuffle instruction and the read-only data cache.Finally,we design a concurrent L1-min solver on multiple GPUs.The experimental results have validated the high effectiveness and good performance of our proposed methods.
基金Sponsored by the National Natural Science Foundation of China(Grant No.61101122)the National High Technology Research and Development Program of China(Grant No.2012AA120802)the National Science and Technology Major Project of the Ministry of Science and Technology of China(Grant No.2012ZX03004-003)
文摘For indoor location estimation based on received signal strength( RSS) in wireless local area networks( WLAN),in order to reduce the influence of noise on the positioning accuracy,a large number of RSS should be collected in offline phase. Therefore,collecting training data with positioning information is time consuming which becomes the bottleneck of WLAN indoor localization. In this paper,the traditional semisupervised learning method based on k-NN and ε-NN graph for reducing collection workload of offline phase are analyzed,and the result shows that the k-NN or ε-NN graph are sensitive to data noise,which limit the performance of semi-supervised learning WLAN indoor localization system. Aiming at the above problem,it proposes a l1-graph-algorithm-based semi-supervised learning( LG-SSL) indoor localization method in which the graph is built by l1-norm algorithm. In our system,it firstly labels the unlabeled data using LG-SSL and labeled data to build the Radio Map in offline training phase,and then uses LG-SSL to estimate user's location in online phase. Extensive experimental results show that,benefit from the robustness to noise and sparsity ofl1-graph,LG-SSL exhibits superior performance by effectively reducing the collection workload in offline phase and improving localization accuracy in online phase.
文摘The generalized l1 greedy algorithm was recently introduced and used to reconstruct medical images in computerized tomography in the compressed sensing framework via total variation minimization. Experimental results showed that this algorithm is superior to the reweighted l1-minimization and l1 greedy algorithms in reconstructing these medical images. In this paper the effectiveness of the generalized l1 greedy algorithm in finding random sparse signals from underdetermined linear systems is investigated. A series of numerical experiments demonstrate that the generalized l1 greedy algorithm is superior to the reweighted l1-minimization and l1 greedy algorithms in the successful recovery of randomly generated Gaussian sparse signals from data generated by Gaussian random matrices. In particular, the generalized l1 greedy algorithm performs extraordinarily well in recovering random sparse signals with nonzero small entries. The stability of the generalized l1 greedy algorithm with respect to its parameters and the impact of noise on the recovery of Gaussian sparse signals are also studied.
基金supported by the National Natural Science Foundation of China(No.61273050)the Aeronautical Science Foundation of China(No.20121352026)
文摘The guidance and control for UAV aerial refueling docking based on dynamic inversion with L1 adaptive augmentation is studied.In order to improve the tracking performance of UAV aerial refueling docking,aguidance algorithm is developed to satisfy the tracking requirement of position and velocity,and it generates the UAV flight control loop commands.In flight control loop,based on the 6-DOF nonlinear model,the angular rate loop and the attitude loop are separated based on time-scale principle and the control law is designed using dynamic inversion.The throttle control is also derived from dynamic inversion method.Moreover,an L1 adaptive augmentation is developed to compensate for the undesirable effects of modeling uncertainty and disturbance.Nonlinear digital simulations are carried out.The results show that the guidance and control system has good tracking performance and robustness in achieving accurate aerial refueling docking.
基金supported by the National Natural Science Foundation of China(grant number 11671081).
文摘With the help of the asymptotic expansion for the classic Li formula and based on the L1-type compact difference scheme,we propose a temporal Richardson extrapolation method for the fractional sub-diffusion equation.Three extrapolation formulas are presented,whose temporal convergence orders in L_(∞)-norm are proved to be 2,3-α,and 4-2α,respectively,where 0<α<1.Similarly,by the method of order reduction,an extrapola-tion method is constructed for the fractional wave equation including two extrapolation formulas,which achieve temporal 4-γ and 6-2γ order in L_(∞)-norm,respectively,where1<γ<2.Combining the derived extrapolation methods with the fast algorithm for Caputo fractional derivative based on the sum-of-exponential approximation,the fast extrapolation methods are obtained which reduce the computational complexity significantly while keep-ing the accuracy.Several numerical experiments confirm the theoretical results.
文摘Compressive sensing(CS)is an emerging methodology in computational signal processing that has recently attracted intensive research activities.At present,the basic CS theory includes recoverability and stability:the former quantifies the central fact that a sparse signal of length n can be exactly recovered from far fewer than n measurements via l1-minimization or other recovery techniques,while the latter specifies the stability of a recovery technique in the presence of measurement errors and inexact sparsity.So far,most analyses in CS rely heavily on the Restricted Isometry Property(RIP)for matrices.In this paper,we present an alternative,non-RIP analysis for CS via l1-minimization.Our purpose is three-fold:(a)to introduce an elementary and RIP-free treatment of the basic CS theory;(b)to extend the current recoverability and stability results so that prior knowledge can be utilized to enhance recovery via l1-minimization;and(c)to substantiate a property called uniform recoverability of l1-minimization;that is,for almost all random measurement matrices recoverability is asymptotically identical.With the aid of two classic results,the non-RIP approach enables us to quickly derive from scratch all basic results for the extended theory.
文摘In this paper, we consider an extragradient thresholding algorithm for finding the sparse solution of mixed complementarity problems (MCPs). We establish a relaxation l1 regularized projection minimization model for the original problem and design an extragradient thresholding algorithm (ETA) to solve the regularized model. Furthermore, we prove that any cluster point of the sequence generated by ETA is a solution of MCP. Finally, numerical experiments show that the ETA algorithm can effectively solve the l1 regularized projection minimization model and obtain the sparse solution of the mixed complementarity problem.
