WorksMathematics
Sparse descent subspace-Newton thresholding algorithm for sparse optimization problems
Abstract
In this paper, we propose a sparse descent direction derived from the Newton direction within a low-dimensional subspace for sparse optimization problems. Building upon this direction and incorporating hard thresholding and orthogonal projection, we develop a novel algorithm termed the sparse descent subspace-Newton thresholding (SDSNT) algorithm. We further establish its global convergence under the restricted isometry property of the measurement matrix. Numerical experiments on random sparse vector recovery and audio signal reconstruction reveal that SDSNT achieves comparable performance to several state-of-the-art algorithms. Notably, relative to most of them, it delivers superior recovery at high sparsity levels and improved efficiency at low sparsity levels.
Introduction
In this paper, we aim to recover a sparse vector from its linear measurements with unknown errors , where is a given measurement matrix with . The recovery of from the data can be formulated as the following sparse optimization problem
where denotes the sparsity level (i.e., the number of nonzero entries) of a vector, and is an estimate of .
Hard thresholding algorithms constitute a mainstream class of sparse optimization methods for solving (1). Gradient descent and Newton’s method are two fundamental approaches to unconstrained optimization. By combining gradient descent with hard thresholding, the iterative hard thresholding (IHT) algorithm [1] was developed for solving (1). While IHT enjoys an extremely low computational cost per iteration, it suffers from slow convergence and high sensitivity to noise. To overcome these drawbacks, the hard thresholding pursuit (HTP) algorithm [4] was proposed by incorporating orthogonal projection into IHT. Among its variants, the heavy-ball-based HTP algorithm was devised by fusing the gradient and momentum directions [9]. While gradient descent is sensitive to poor scaling, Newton’s method is largely unaffected by it and usually exhibits faster local convergence [8]. By integrating Newton’s method with hard thresholding, the Newton-step-based HTP algorithm was developed in [5]. Since this algorithm requires computing the inverse of the modified Hessian , where the Hessian is singular, is the identity matrix and , its computational cost becomes prohibitive for high-dimensional problems. To reduce the computational cost and circumvent the Hessian singularity, the compressed Newton-direction-based thresholding pursuit algorithm was introduced in [6], which projects the Newton step onto a lower-dimensional subspace and subsequently maps it back to the original space via diagonal regularization. Furthermore, the combination of the restricted Newton and gradient directions was utilized to design the Newton HTP (NHTP) algorithm [12]. An analogous method has also been developed for sparse optimization problems with box constraints [10].
Additionally, full gradient descent coincides with partial gradient descent under certain conditions for sparse optimization. In what follows, we take HTP as an example to illustrate this. HTP is briefly summarized as follows:
where is the negative gradient at the current point , and () is the index set for the largest absolute entries of a vector. Moreover, the supports of and are disjoint due to the first-order optimality condition of (3). Thus, (2) is equivalent to for any integers , where and is a -sparse vector which retains the elements of with indices lying in and sets the others to zero. That is, the partial gradient (or sparse descent direction) can serve as a replacement for its full-gradient counterpart in HTP. Inspired by this observation, we integrate the sparse descent direction with the subspace Newton method to propose the sparse descent subspace-Newton thresholding (SDSNT) algorithm. We establish the global convergence of SDSNT under the restricted isometry property . Moreover, numerical results on synthetic and real data reveal that SDSNT achieves comparable performance to several algorithms, including NHTP [12], HTP [4], natural thresholding pursuit (NTP) [11], subspace pursuit (SP) [3], and compressive sampling matching pursuit (CoSaMP) [7] algorithms. The paper is organized as follows. In § 2, we introduce some notation, definition, basic inequalities and the proposed algorithm. In § 3, the global convergence of SDSNT is rigorously proved. In § 4, numerical experiments on synthetic data and audio signal data are conducted. The conclusion is summarized in the final section.
Preliminary and algorithm
Preliminary
Let be the index set . For any set , we write for the cardinality of , and for the complement of in . Given , is referred to as the support of . Let be the index set for the largest absolute entries of . If , then is said to be -sparse. For and , we use to denote two related vectors, depending on context: 1. the masked vector in that preserves for and sets for ; 2. the compressed vector in formed by extracting only the entries with and discarding the rest. We write for the submatrix of consisting of columns indexed by . Let denote the identity matrix, whose dimension can be determined from the context.
The following definition was originally proposed in [2 definition 1.1] and is essential for analyzing our algorithm.
Definition 2.1. [2] Given a matrix with . If there exists a smallest constant such that
for any -sparse vector , the matrix is said to satisfy the restricted isometry property (RIP) of order . Moreover, is known as the restricted isometry constant (RIC) of order , and it admits an equivalent form [4]:
Two basic inequalities given in the following lemma will be frequently used in the next section.
Lemma 2.2. [4] Let and be two vectors, be a positive integer and be an index set.
(i) If , then .
(ii) If , then .
Algorithm
From Definition 2.1, under the RIP of order , the principal submatrix of the Hessian is positive definiteness for any with . Accordingly, we construct a sparse descent direction as follows: and , with being the Newton direction in the -dimensional coordinate subspace associated with . It can be regarded as a special case of the compressed Newton search direction with in [6]; however, both the algorithmic framework and its convergence analysis in [6] were established only for . By embedding the sparse direction into the hard thresholding framework, we propose the SDSNT algorithm for sparse optimization problems.
Global convergence
The following lemma can be obtained by Eq. (3.21) in [4] and Eq. (3.17) in [9] directly.
Lemma 3.1. [4, 9] Given vectors , the index sets and , and the noisy measurements of , where is the noise vector. The iterate generated by (6) obeys
where , and
Algorithm 1 Sparse descent subspace-Newton thresholding (SDSNT) algorithm
Input , stepsize and initial point .
S1. Let , , and . Set
where
S2. Let , and
The above steps continue to be looped unless a stopping criterion is reached.
where is the symmetric difference of and $S.
The error bound for SDSNT is established in the following theorem.
Theorem 3.2. Suppose that the RIC, , of the matrix and the stepsize satisfy that
where the constants are given as follows,
and . Let be the measurements of with errors . Then the iterates generated by SDSNT satisfies
where , , and , are given as
where .
Proof. Denote and , where , , and . From SDSNT algorithm, we have , which in turn implies . It follows from Lemma 3.1 that
Next, we aim to estimate the upper bound of by and . Note that can be split into two disjoint sets and .
Firstly, we estimate the upper bound of . From the orthogonality of (6), we see that , which implies that and . From (4) and (5), we obtain
where the last equality is given by . Since and , we get
where the equality results from and . Merging (12) and (13) leads to
where the last inequality results from and . Since , we have
where . Since and , from (15) and Lemma 2.2, we obtain
Combining (14) and (16), we get
Secondly, we estimate the upper bound of . From (4), (5) and (15), we obtain
where the third equality is given by and . Since , thus is a submatrix of . Hence,
where the last inequality results from Definition 2.1 with . From Definition 2.1, the eigenvalues of lie in , and thus those of belong to . Hence, . Combining this bound with (18) and (19), we arrive at
where the last inequality is obtained by the first equality of (12) and Lemma 2.2 with . For and , the following inequality holds:
where the last inequality results form . Combining (20) and (21), we find
where is given in Theorem 3.2. It follows from (17) that
Substituting (22) into (11), we get
where , are given in (10) and the last inequality is given by . It means that (9) holds.
Finally, we prove that under the conditions in (7). Denote , . Since is strictly increasing on , it follows from (8) and (7) that
where the last inequality is easily verified and thus omitted. Hence, , which implies that the second inequality in (7) is well defined. Since , (10) implies that
where the equality is given by (8). It is easy to check that the following inequality
holds for any . Combining (24) and (25) with leads to
where the equality is given by the definition of in (8). It follows from (7) that . □
The global convergence of SDSNT follows directly from Theorem 3.2 under certain conditions; see Remark 3.3.
Remark 3.3. If is a -sparse vector and its measurement vector is accurate, i.e., and , then (9) reduces to , where is given by (10). Consequently, the iterates generated by SDSNT converges to .
Experiments
In the following experiments, we compare the proposed algorithm with several state-of-the-art algorithms, including NHTP [12], HTP [4], NTP [11], SP [3], and CoSaMP [7], in terms of random sparse vector recovery and audio signal reconstruction. The stepsizes of SDSNT and HTP are set to 4 and 1, respectively. The algorithm parameters of NTP and NHTP are set identically to the original paper. Throughout this section, the problem dimension and the number of measurements are fixed at and . The measurement matrix is randomly generated, and its elements are sampled independently from .
Recovery of random sparse vector
We first evaluate the recovery performance of the algorithms on 100 random instances for each sparsity level , ranging from 600 to 1500 with stepsize 20. For each instance, the noisy measurements of a -sparse vector are generated by , where is a normalized Gaussian noise vector and . The nonzero positions of are uniformly distributed, with values drawn independently from . We aim to recover from the data , and a recovery is deemed successful if the solution produced by an algorithm satisfies , which is also adopted as the stopping criterion. All algorithms are allowed up to 50 iterations. Figure 1 illustrates the success rates and average runtimes of all algorithms under comparison. Notably, the average CPU time for successful recovery is recorded only for algorithms with a success rate of at least 0.9. Figure 1(a) indicates that SDSNT and NTP exhibit comparable recovery performance and both outperform the other four algorithms, with a marked advantage over CoSaMP. On the other hand, Figure 1(b) shows that SDSNT is always faster than CoSaMP and SP, but slower than HTP. For , SDSNT exhibits lower computational cost than NHTP; however, when increases beyond this threshold, its average CPU time gradually surpasses that of NHTP. A similar pattern holds for NTP with . The above results reveal that SDSNT achieves superior computational efficiency at low sparsity levels.

Figure 1. Success rates and average CPU times of the algorithms
Reconstruction of audio signal
In this subsection, we investigate the reconstruction of an audio signal depicted in Figure 2(b). This signal is transformed into a compressible vector via the orthogonal transform , i.e., . Here, stands for the discrete cosine transform, and denotes the three-level discrete wavelet transform based on the ‘sym12’ wavelet with periodic extension. Given measurements of the signal , we reconstruct a -sparse vector from the data using an algorithm with , where is the best -term approximation of . Consequently, the reconstructed signal is given by . We use the signal-to-noise ratio (SNR), defined by , to evaluate the quality of the reconstructed signal. Each algorithm is allowed a maximum CPU time of 10 seconds. Figure 2(a) shows the SNR versus the CPU time for all compared algorithms, with the per-iteration runtime recorded for each algorithm. The maximum SNR values attained by SDSNT, NHTP, HTP, NTP, SP and CoSaMP are approximately 26, 25, 25, 26, 23 and 14, respectively. Except for NTP, SDSNT achieves a maximum SNR at least 1 dB higher than that of any other algorithm. This superior SNR translates into better signal fidelity, as evidenced in Figure 2(b), where the signal reconstructed by SDSNT closely matches the original audio signal.

Figure 2. (a) Comparison of SNR (in dB) vs. CPU time (in seconds); (b) The original audio signal and the reconstructed one by SDSNT.
Conclusions
The SDSNT algorithm was proposed by combining a sparse descent direction with hard thresholding and orthogonal projection, in which the direction is derived from the Newton direction within a low-dimensional subspace. This approach involves computing the principal submatrix of the Hessian that is positive definite under the RIP, thereby circumventing the singularity of the Hessian. The global convergence of SDSNT has been established under the RIP and with an appropriate stepsize. Numerical results show that SDSNT can compete with several state-of-the-art algorithms in terms of both recovery capability and computational efficiency.
Data availability
The data will be openly available at the following URL after publication: https://github.com/zhongfengsun/zhongfengsun.github.io/tree/gh-
Acknowledgments
This work was supported by Shandong Provincial Natural Science Foundation (ZR2025MS99, ZR2023MA020), the National Natural Science Foundation of China (12371305, 12301400, 12471295, 12426306), Guangdong Basic and Applied Basic Research Foundation (2024A1515011566), and Hetao Shenzhen-Hong Kong Science and Technology Innovation Cooperation Zone Project (HZQSWS-KCCYB-2024016).
References
- [1]T. Blumensath, M.E. Davies, Iterative thresholding for sparse approximations, J. Fourier Anal. Appl. 14 (2008) 629–654.DOI
- [2]E.J. Candès, T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51(12) (2005) 4203–4215.DOI
- [3]W. Dai, O. Milenkovic, Subspace pursuit for compressive sensing signal reconstruction, IEEE Trans. Inform. Theory 55(5) (2009) 2230–2249.arxiv.org/abs/0803.0811
- [4]S. Foucart, Hard thresholding pursuit: An algorithm for compressive sensing, SIAM J. Numer. Anal. 49 (6) (2011) 2543–2563.DOI
- [5]N. Meng, Y.B. Zhao, Newton-step-based hard thresholding algorithms for sparse signal recovery, IEEE Trans. Signal Process. 68 (2020) 6594–6606.DOI
- [6]N. Meng, Y.B. Zhao, Compressed Newton-direction-based thresholding methods for sparse optimization problems, J. Glob. Optim. 96 (2026) 115–140.arxiv.org/abs/2510.04451
- [7]D. Needell, J.A. Tropp, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal. 26 (3)(2009) 301–321.
- [8]J. Nocedal, S.J. Wright, Numerical Optimization, Springer, New York, 2006.
- [9]Z.F. Sun, J.C. Zhou, Y.B. Zhao, N. Meng, Heavy-ball-based hard thresholding algorithms for sparse signal recovery, J. Comput. Appl. Math. 430 (2023) 115264.arxiv.org/abs/2204.09300
- [10]Y. Ye, Q. Li, Subspace Newton’s method for ℓ₀-regularized optimization problems with box constraints, J. Sci. Comput. 106 (2026) 68.DOI
- [11]Y.B. Zhao, Z.Q. Luo, Natural thresholding algorithms for signal recovery with sparsity, IEEE Open J. Signal Process. 3 (2022) 417–431.arxiv.org/abs/2207.09622
- [12]S. Zhou, N. Xiu, H.D. Qi, Global and quadratic convergence of Newton hard-thresholding pursuit, J. Mach. Learn. Res. 22(12) (2021) 1-45.