Shor’s algorithm outperforms its classical counterpart in efficient prime factorization. We explore the coherence and entanglement dynamics of the evolved states within Shor’s algorithm, showing that the coherence i...Shor’s algorithm outperforms its classical counterpart in efficient prime factorization. We explore the coherence and entanglement dynamics of the evolved states within Shor’s algorithm, showing that the coherence in each step relies on the dimension of register or the order, and discuss the relations between geometric coherence and geometric entanglement. We investigate how unitary operators induce variations in coherence and entanglement, and analyze the variations of coherence and entanglement within the entire algorithm, demonstrating that the overall effect of Shor’s algorithm tends to deplete coherence and produce entanglement. Our research not only deepens the understanding of this algorithm but also provides methodological references for studying resource dynamics in other quantum algorithms.展开更多
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.展开更多
In this paper,we propose an adaptive algorithm for L1-fidelity color image restoration by using saturation-value total variation.The main contribution of this paper is to employ the generalized cross validation method...In this paper,we propose an adaptive algorithm for L1-fidelity color image restoration by using saturation-value total variation.The main contribution of this paper is to employ the generalized cross validation method efficiently and automatically to estimate the regularization parameter in a saturation-value total variation plus L1-fidelity color image restoration model.We consider Poisson noise and mixed noise in this paper,and the experimental results show that the visual quality and the SSIM/PSNR/SAM values of the restored images by using the proposed algorithm are competitive with other tested existing methods,which makes the proposed algorithm to be comparable both quantitatively and qualitatively.展开更多
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.展开更多
A hybrid Compressed Sensing and Primal-Dual Wavelet(CSP-PDW)technique is proposed for the compression and reconstruction of ECG signals.The compression and reconstruction algorithms are implemented using four key conc...A hybrid Compressed Sensing and Primal-Dual Wavelet(CSP-PDW)technique is proposed for the compression and reconstruction of ECG signals.The compression and reconstruction algorithms are implemented using four key concepts:Sparsifying Basis,Restricted Isometry Principle,Gaussian Random Matrix,and Convex Minimization.In addition to the conventional compression sensing reconstruction approach,wavelet-based processing is employed to enhance reconstruction efficiency.A mathematical model of the proposed algorithm is derived analytically to obtain the essential parameters of compression sensing,including the sparsifying basis,measurement matrix size,and number of iterations required for reconstructing the original signal and determining the type and level of wavelet processing.The low time complexity of the proposed algorithm makes it an ideal candidate for ECG monitoring systems in IoT-based e-healthcare applications.A feature extraction algorithm is also developed to show that the important ECG peaks remain unaltered after reconstruction.The clinical relevance of the reconstructed signal and the efficiency of the developed algorithm are evaluated using four validation parameters at three different compression ratios.展开更多
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.展开更多
Truncated L1 regularization proposed by Fan in[5],is an approximation to the L0 regularization in high-dimensional sparse models.In this work,we prove the non-asymptotic error bound for the global optimal solution to ...Truncated L1 regularization proposed by Fan in[5],is an approximation to the L0 regularization in high-dimensional sparse models.In this work,we prove the non-asymptotic error bound for the global optimal solution to the truncated L1 regularized linear regression problem and study the support recovery property.Moreover,a primal dual active set algorithm(PDAS)for variable estimation and selection is proposed.Coupled with continuation by a warm-start strategy leads to a primal dual active set with continuation algorithm(PDASC).Data-driven parameter selection rules such as cross validation,BIC or voting method can be applied to select a proper regularization parameter.The application of the proposed method is demonstrated by applying it to simulation data and a breast cancer gene expression data set(bcTCGA).展开更多
Recently, the 1-bit compressive sensing (1-bit CS) has been studied in the field of sparse signal recovery. Since the amplitude information of sparse signals in 1-bit CS is not available, it is often the support or ...Recently, the 1-bit compressive sensing (1-bit CS) has been studied in the field of sparse signal recovery. Since the amplitude information of sparse signals in 1-bit CS is not available, it is often the support or the sign of a signal that can be exactly recovered with a decoding method. We first show that a necessary assumption (that has been overlooked in the literature) should be made for some existing theories and discussions for 1-bit CS. Without such an assumption, the found solution by some existing decoding algorithms might be inconsistent with 1-bit measurements. This motivates us to pursue a new direction to develop uniform and nonuniform recovery theories for 1-bit CS with a new decoding method which always generates a solution consistent with 1-bit measurements. We focus on an extreme case of 1-bit CS, in which the measurements capture only the sign of the product of a sensing matrix and a signal. We show that the 1-bit CS model can be reformulated equivalently as an t0-minimization problem with linear constraints. This reformulation naturally leads to a new linear-program-based decoding method, referred to as the 1-bit basis pursuit, which is remarkably different from existing formulations. It turns out that the uniqueness condition for the solution of the 1-bit basis pursuit yields the so-called restricted range space property (RRSP) of the transposed sensing matrix. This concept provides a basis to develop sign recovery conditions for sparse signals through 1-bit measurements. We prove that if the sign of a sparse signal can be exactly recovered from 1-bit measurements with 1-bit basis pursuit, then the sensing matrix must admit a certain RRSP, and that if the sensing matrix admits a slightly enhanced RRSP, then the sign of a k-sparse signal can be exactly recovered with 1-bit basis pursuit.展开更多
基金supported by National Natural Science Foundation of China(Grant Nos.12161056,12075159,12171044)Natural Science Foundation of Jiangxi Province(Grant No.20232ACB211003)+1 种基金Beijing Natural Science Foundation(Grant No.Z190005)the specific research fund of the Innovation Platform for Academicians of Hainan Province.
摘要Shor’s algorithm outperforms its classical counterpart in efficient prime factorization. We explore the coherence and entanglement dynamics of the evolved states within Shor’s algorithm, showing that the coherence in each step relies on the dimension of register or the order, and discuss the relations between geometric coherence and geometric entanglement. We investigate how unitary operators induce variations in coherence and entanglement, and analyze the variations of coherence and entanglement within the entire algorithm, demonstrating that the overall effect of Shor’s algorithm tends to deplete coherence and produce entanglement. Our research not only deepens the understanding of this algorithm but also provides methodological references for studying resource dynamics in other quantum algorithms.
基金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 Natural Science Foundation of Shanghai(Grant No.22ZR1465300).
摘要In this paper,we propose an adaptive algorithm for L1-fidelity color image restoration by using saturation-value total variation.The main contribution of this paper is to employ the generalized cross validation method efficiently and automatically to estimate the regularization parameter in a saturation-value total variation plus L1-fidelity color image restoration model.We consider Poisson noise and mixed noise in this paper,and the experimental results show that the visual quality and the SSIM/PSNR/SAM values of the restored images by using the proposed algorithm are competitive with other tested existing methods,which makes the proposed algorithm to be comparable both quantitatively and qualitatively.
基金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.
摘要A hybrid Compressed Sensing and Primal-Dual Wavelet(CSP-PDW)technique is proposed for the compression and reconstruction of ECG signals.The compression and reconstruction algorithms are implemented using four key concepts:Sparsifying Basis,Restricted Isometry Principle,Gaussian Random Matrix,and Convex Minimization.In addition to the conventional compression sensing reconstruction approach,wavelet-based processing is employed to enhance reconstruction efficiency.A mathematical model of the proposed algorithm is derived analytically to obtain the essential parameters of compression sensing,including the sparsifying basis,measurement matrix size,and number of iterations required for reconstructing the original signal and determining the type and level of wavelet processing.The low time complexity of the proposed algorithm makes it an ideal candidate for ECG monitoring systems in IoT-based e-healthcare applications.A feature extraction algorithm is also developed to show that the important ECG peaks remain unaltered after reconstruction.The clinical relevance of the reconstructed signal and the efficiency of the developed algorithm are evaluated using four validation parameters at three different compression ratios.
基金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.
摘要Truncated L1 regularization proposed by Fan in[5],is an approximation to the L0 regularization in high-dimensional sparse models.In this work,we prove the non-asymptotic error bound for the global optimal solution to the truncated L1 regularized linear regression problem and study the support recovery property.Moreover,a primal dual active set algorithm(PDAS)for variable estimation and selection is proposed.Coupled with continuation by a warm-start strategy leads to a primal dual active set with continuation algorithm(PDASC).Data-driven parameter selection rules such as cross validation,BIC or voting method can be applied to select a proper regularization parameter.The application of the proposed method is demonstrated by applying it to simulation data and a breast cancer gene expression data set(bcTCGA).
基金supported by the Engineering and Physical Sciences Research Council of UK (Grant No. #EP/K00946X/1)
摘要Recently, the 1-bit compressive sensing (1-bit CS) has been studied in the field of sparse signal recovery. Since the amplitude information of sparse signals in 1-bit CS is not available, it is often the support or the sign of a signal that can be exactly recovered with a decoding method. We first show that a necessary assumption (that has been overlooked in the literature) should be made for some existing theories and discussions for 1-bit CS. Without such an assumption, the found solution by some existing decoding algorithms might be inconsistent with 1-bit measurements. This motivates us to pursue a new direction to develop uniform and nonuniform recovery theories for 1-bit CS with a new decoding method which always generates a solution consistent with 1-bit measurements. We focus on an extreme case of 1-bit CS, in which the measurements capture only the sign of the product of a sensing matrix and a signal. We show that the 1-bit CS model can be reformulated equivalently as an t0-minimization problem with linear constraints. This reformulation naturally leads to a new linear-program-based decoding method, referred to as the 1-bit basis pursuit, which is remarkably different from existing formulations. It turns out that the uniqueness condition for the solution of the 1-bit basis pursuit yields the so-called restricted range space property (RRSP) of the transposed sensing matrix. This concept provides a basis to develop sign recovery conditions for sparse signals through 1-bit measurements. We prove that if the sign of a sparse signal can be exactly recovered from 1-bit measurements with 1-bit basis pursuit, then the sensing matrix must admit a certain RRSP, and that if the sensing matrix admits a slightly enhanced RRSP, then the sign of a k-sparse signal can be exactly recovered with 1-bit basis pursuit.