betaFeedback

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 δ3k≤3/20δ_{3k}\leq \sqrt{3/20} 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 x∈Rnx \in\mathbb{R}^{n} from its linear measurements y=Ax+ν∈Rmy = Ax + \nu\in\mathbb{R}^{m} with unknown errors ν∈Rm\nu\in\mathbb{R}^{m}, where A∈Rm×nA \in\mathbb{R}^{m \times n} is a given measurement matrix with m≪nm \ll n. The recovery of xx from the data (y,A)(y,A) can be formulated as the following sparse optimization problem

arg min⁡z∈Rn{12∥y−Az∥22: ∥z∥0≤k},(1)\underset{z \in\mathbb{R}^{n}}{\operatorname{arg\,min}}\left\{\frac{1}{2}\lVert y-Az\rVert_{2}^{2}:\ \lVert z\rVert_{0} \le k\right\}, \tag*{(1)}

where ∥⋅∥0\lVert\cdot\rVert_{0} denotes the sparsity level (i.e., the number of nonzero entries) of a vector, and kk is an estimate of ∥x∥0\lVert x\rVert_{0}.

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 (ATA+εI)−1(A^{T}A+\varepsilon I)^{-1}, where the Hessian ATAA^{T}A is singular, II is the identity matrix and ε>0\varepsilon> 0, 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:

Sp+1=Lk(xp+dp),(2)S^{p+1}=\mathcal{L}_{k}(x^{p}+d^{p}), \tag*{(2)}
xp+1=arg min⁡z∈Rn{12∥y−Az∥22: supp⁡(z)⊆Sp+1},(3)x^{p+1}=\underset{z\in\mathbb{R}^{n}}{\operatorname{arg\,min}}\left\{\frac{1}{2}\lVert y-Az\rVert_{2}^{2}:\ \operatorname{supp}(z)\subseteq S^{p+1}\right\}, \tag*{(3)}

where dpd^p is the negative gradient at the current point xpx^p, and Lq(⋅)\mathcal{L}_q(\cdot) (q≥1q \ge1) is the index set for the qq largest absolute entries of a vector. Moreover, the supports of xpx^p and dpd^p are disjoint due to the first-order optimality condition of (3). Thus, (2) is equivalent to Sp+1=Lk(xp+(dp)Ωq)S^{p+1}=\mathcal{L}_k(x^p+(d^p)_{\Omega_q}) for any integers q∈[k,n)q \in[k,n), where Ωq=Lq(dp)\Omega_q=\mathcal{L}_q(d^p) and (dp)Ωq(d^p)_{\Omega_q} is a qq-sparse vector which retains the elements of dpd^p with indices lying in Ωq\Omega_q 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 δ3k≤3/20\delta_{3k}\le\sqrt{3}/20. 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 NN be the index set {1,…,n}\{1,\ldots,n\}. For any set S⊆NS\subseteq N, we write ∣S∣|S| for the cardinality of SS, and S‾=N∖S\overline{S}=N\setminus S for the complement of SS in NN. Given x=(x1,…,xn)T∈Rnx=(x_1,\ldots,x_n)^T\in\mathbb{R}^n, supp⁡(x)={i:xi≠0}\operatorname{supp}(x)=\{i:x_i\ne0\} is referred to as the support of xx. Let Ls(x)\mathcal{L}_s(x) be the index set for the ss largest absolute entries of xx. If ∣supp⁡(x)∣≤s|\operatorname{supp}(x)|\le s, then xx is said to be ss-sparse. For x∈Rnx\in\mathbb{R}^n and S⊆NS\subseteq N, we use xSx_S to denote two related vectors, depending on context: 1. the masked vector in Rn\mathbb{R}^n that preserves xix_i for i∈Si\in S and sets xi=0x_i=0 for i∉Si\notin S; 2. the compressed vector in R∣S∣\mathbb{R}^{|S|} formed by extracting only the entries xix_i with i∈Si\in S and discarding the rest. We write ASA_S for the submatrix of A∈Rm×nA\in\mathbb{R}^{m\times n} consisting of columns indexed by SS. Let II 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 A∈Rm×nA\in\mathbb{R}^{m\times n} with m≪nm\ll n. If there exists a smallest constant 0≤δs<10\le\delta_s<1 such that

(1−δs)∥x∥22≤∥Ax∥22≤(1+δs)∥x∥22(1-\delta_s)\lVert x\rVert_2^2\le\lVert Ax\rVert_2^2\le(1+\delta_s)\lVert x\rVert_2^2

for any ss-sparse vector x∈Rnx\in\mathbb{R}^n, the matrix AA is said to satisfy the restricted isometry property (RIP) of order ss. Moreover, δs\delta_s is known as the restricted isometry constant (RIC) of order ss, and it admits an equivalent form [4]:

δs=max⁡S⊆N, ∣S∣≤s∥ASTAS−I∥2.\delta_s=\max_{S\subseteq N,\ |S|\le s}\lVert A_S^TA_S-I\rVert_2.

Two basic inequalities given in the following lemma will be frequently used in the next section.

Lemma 2.2. [4] Let u∈Rnu\in\mathbb{R}^n and v∈Rmv\in\mathbb{R}^m be two vectors, s∈Ns\in N be a positive integer and W⊆NW\subseteq N be an index set.

(i) If ∣W∪supp⁡(u)∣≤s|W\cup\operatorname{supp}(u)|\le s, then ∥((I−ATA)u)W∥2≤δs∥u∥2\lVert((I-A^TA)u)_W\rVert_2\le\delta_s\lVert u\rVert_2.

(ii) If ∣W∣≤s|W|\le s, then ∥(ATv)W∥2≤1+δs∥v∥2\lVert(A^Tv)_W\rVert_2\le\sqrt{1+\delta_s}\lVert v\rVert_2.

Algorithm

From Definition 2.1, under the RIP of order ss, the principal submatrix ASTASA_S^TA_S of the Hessian is positive definiteness for any S⊆NS\subseteq N with ∣S∣=s|S|=s. Accordingly, we construct a sparse descent direction d∈Rnd\in\mathbb{R}^n as follows: dS‾=0d_{\overline{S}}=0 and dS=(ASTAS)−1AST(y−Ax)d_S=(A_S^TA_S)^{-1}A_S^T(y-Ax), with dSd_S being the Newton direction in the ss-dimensional coordinate subspace associated with SS. It can be regarded as a special case of the compressed Newton search direction dCNd_{\mathrm{CN}} with γ=0\gamma=0 in [6]; however, both the algorithmic framework and its convergence analysis in [6] were established only for γ>0\gamma>0. By embedding the sparse direction dd 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 x,up∈Rnx,u^p\in\mathbb{R}^n, the index sets S=Lk(x)S=\mathcal{L}_k(x) and Sp+1=Lk(up)S^{p+1}=\mathcal{L}_k(u^p), and the noisy measurements y=Ax+v∈Rmy=Ax+v\in\mathbb{R}^m of xx, where vv is the noise vector. The iterate xp+1x^{p+1} generated by (6) obeys

∥xp+1−xS∥2≤11−δ2k2∥(xp+1−xS)Sp+1∥2+1+δk1−δ2k∥v′∥2,\lVert x^{p+1}-x_S\rVert_2\le\frac{1}{\sqrt{1-\delta_{2k}^2}}\lVert(x^{p+1}-x_S)_{S^{p+1}}\rVert_2+\frac{\sqrt{1+\delta_k}}{1-\delta_{2k}}\lVert v'\rVert_2,

where v′=v+AxS‾v'=v+Ax_{\overline{S}}, and

∥(xp+1−xS)Sp+1∥2≤2∥(up−xS)Sp+1△S∥2,\lVert(x^{p+1}-x_S)_{S^{p+1}}\rVert_2\le\sqrt{2}\lVert(u^p-x_S)_{S^{p+1}\mathbin{\triangle} S}\rVert_2,

Algorithm 1 Sparse descent subspace-Newton thresholding (SDSNT) algorithm

Input (A,y,k)(A,y,k), stepsize α>0\alpha> 0 and initial point x0=0x^0 = 0.

S1. Let rp=AT(y−Axp)r^p=A^{T}(y-Ax^p), Ωk=Lk(rp)\Omega_k=\mathcal{L}_k(r^p), and Mp=(AΩkTAΩk)−1M^p=(A_{\Omega_k}^{T}A_{\Omega_k})^{-1}. Set

up=xp+α⋅dp,(4)u^p=x^p+\alpha\cdot d^p, \tag*{(4)}

where

(dp)Ωk=Mp⋅(rp)Ωk,(dp)Ω‾k=0.(5)(d^p)_{\Omega_k}=M^p\cdot(r^p)_{\Omega_k},\qquad(d^p)_{\overline{\Omega}_k}=0. \tag*{(5)}

S2. Let Sp+1=Lk(up)S^{p+1}=\mathcal{L}_k(u^p), and

xp+1=arg⁡min⁡z∈Rn{12∥y−Az∥22:supp⁡(z)⊆Sp+1}.(6)x^{p+1}=\mathop{\arg\min}_{z\in\mathbb{R}^{n}}\left\{\frac{1}{2}\lVert y-Az\rVert_2^2:\operatorname{supp}(z)\subseteq S^{p+1}\right\}. \tag*{(6)}

The above steps continue to be looped unless a stopping criterion is reached.

where Sp+1△S:=(Sp+1∖S)∪(S∖Sp+1)S^{p+1}\triangle S:=(S^{p+1}\setminus S)\cup(S\setminus S^{p+1}) is the symmetric difference of Sp+1S^{p+1} and $S.

The error bound for SDSNT is established in the following theorem.

Theorem 3.2. Suppose that the RIC, δ3k\delta_{3k}, of the matrix AA and the stepsize α\alpha satisfy that

δ3k≤320,1−C1−C31+2δ3k−C3<α<1+C1−C32δ3kC2+1,(7)\delta_{3k}\le\sqrt{\frac{3}{20}},\qquad1-\frac{C_1-C_3}{1+\sqrt{2}\delta_{3k}-C_3}<\alpha<1+\frac{C_1-C_3}{\sqrt{2}\delta_{3k}C_2+1}, \tag*{(7)}

where the constants Ci,i=1,2,3C_i,i=1,2,3 are given as follows,

C1=1−δ3k22,C2=δ3k1−δ3k,C3=2δ3k1+C22,(8)C_1=\sqrt{\frac{1-\delta_{3k}^{2}}{2}},\qquad C_2=\frac{\delta_{3k}}{1-\delta_{3k}},\qquad C_3=\sqrt{2}\delta_{3k}\sqrt{1+C_2^2}, \tag*{(8)}

and C3<C1<1C_3<C_1<1. Let y=Ax+νy=Ax+\nu be the measurements of xx with errors ν\nu. Then the iterates {xp}\{x^p\} generated by SDSNT satisfies

∥xp+1−xS∥2≤ρ∥xp−xS∥2+C∥ν′∥2,(9)\lVert x^{p+1}-x_S\rVert_2\le\rho\lVert x^p-x_S\rVert_2+C\lVert\nu'\rVert_2, \tag*{(9)}

where S=Lk(x)S=\mathcal{L}_k(x), ν′=ν+AxS‾\nu'=\nu+Ax_{\overline{S}}, and ρ\rho, CC are given as

ρ=21−δ2k2(∣1−α∣+2δ3kC4)<1,C=11−δ3k(2C4+2α1−δk)+1+δk1−δ2k,(10)\rho=\frac{\sqrt{2}}{\sqrt{1-\delta_{2k}^{2}}}\left(\lvert1-\alpha\rvert+\sqrt{2}\delta_{3k}C_4\right)<1,\qquad C=\frac{1}{\sqrt{1-\delta_{3k}}}\left(2C_4+\frac{\sqrt{2\alpha}}{1-\delta_k}\right)+\frac{\sqrt{1+\delta_k}}{1-\delta_{2k}}, \tag*{(10)}

where C4=(αδ3k1−δk)2+1C_4=\sqrt{\left(\frac{\alpha\delta_{3k}}{1-\delta_k}\right)^2+1}.

Proof. Denote Qp:=supp⁡(xp)Q^p:=\operatorname{supp}(x^p) and W:=S∪Qp∪ΩkW:=S\cup Q^p\cup\Omega_k, where S=Lk(x)S=\mathcal{L}_k(x), Ωk=Lk(rp)\Omega_k=\mathcal{L}_k(r^p), ∣Qp∣≤k\lvert Q^p\rvert\le k and ∣S∣=∣Ωk∣=k\lvert S\rvert=\lvert\Omega_k\rvert=k. From SDSNT algorithm, we have Sp+1⊆supp⁡(up)⊆Qp∪ΩkS^{p+1}\subseteq\operatorname{supp}(u^p)\subseteq Q^p\cup\Omega_k, which in turn implies (Sp+1∖S)∪(S∖Sp+1)⊆Sp+1∪S⊆W(S^{p+1}\setminus S)\cup(S\setminus S^{p+1})\subseteq S^{p+1}\cup S\subseteq W. It follows from Lemma 3.1 that

∥xp+1−xS∥2≤21−δ2k2∥(up−xS)W∥2+1+δk1−δ2k∥ν′∥2.(11)\lVert x^{p+1}-x_S\rVert_2\le\frac{\sqrt{2}}{\sqrt{1-\delta_{2k}^{2}}}\lVert(u^p-x_S)_W\rVert_2+\frac{\sqrt{1+\delta_k}}{1-\delta_{2k}}\lVert\nu'\rVert_2. \tag*{(11)}

Next, we aim to estimate the upper bound of ∥(up−xS)W∥2\lVert(u^p-x_S)_W\rVert_2 by ∥xp−xS∥2\lVert x^p-x_S\rVert_2 and ∥ν′∥2\lVert\nu'\rVert_2. Note that WW can be split into two disjoint sets (S∪Qp)∖Ωk(S\cup Q^p)\setminus\Omega_k and Ωk\Omega_k.

Firstly, we estimate the upper bound of ∥(up−xS)(S∪Qp)∖Ωk∥2\lVert(u^p-x_S)_{(S\cup Q^p)\setminus\Omega_k}\rVert_2. From the orthogonality of (6), we see that Qp∩supp⁡(rp)=∅Q^p\cap\operatorname{supp}(r^p)=\varnothing, which implies that (rp)Qp=0(r^p)_{Q^p}=0 and (xp)Ωk=0(x^p)_{\Omega_k}=0. From (4) and (5), we obtain

(up−xS)(S∪Qp)∖Ωk=(xp−xS)(S∪Qp)∖Ωk=(xp−xS+rp)(S∪Qp)∖Ωk−(rp)(S∪Qp)∖Ωk=(xp−xS+rp)(S∪Qp)∖Ωk−(rp)S∖Ωk,(12)\begin{aligned} (u^p-x_S)_{(S\cup Q^p)\setminus\Omega_k} &=(x^p-x_S)_{(S\cup Q^p)\setminus\Omega_k}\\ &=(x^p-x_S+r^p)_{(S\cup Q^p)\setminus\Omega_k}-(r^p)_{(S\cup Q^p)\setminus\Omega_k}\\ &=(x^p-x_S+r^p)_{(S\cup Q^p)\setminus\Omega_k}-(r^p)_{S\setminus\Omega_k}, \tag*{(12)} \end{aligned}

where the last equality is given by (rp)Qp=0(r^p)_{Q^p}=0. Since Ωk=Lk(rp)\Omega_k=\mathcal{L}_k(r^p) and ∣S∣=∣Ωk∣=k\lvert S\rvert=\lvert\Omega_k\rvert=k, we get

∥(rp)S∖Ωk∥2≤∥(rp)Ωk∖S∥2=∥(xp−xS+rp)Ωk∖S∥2,(13)\lVert(r^p)_{S\setminus\Omega_k}\rVert_2\le\lVert(r^p)_{\Omega_k\setminus S}\rVert_2=\lVert(x^p-x_S+r^p)_{\Omega_k\setminus S}\rVert_2, \tag*{(13)}

where the equality results from (xp)Ωk∖S=0(x^p)_{\Omega_k\setminus S}=0 and (xS)Ωk∖S=0(x_S)_{\Omega_k\setminus S}=0. Merging (12) and (13) leads to

∥(up−xS)(S∪Qp)∖Ωk∥2≤∥(xp−xS+rp)(S∪Qp)∖Ωk∥2+∥(xp−xS+rp)Ωk∖S∥2≤2∥(xp−xS+rp)(S∪Qp)∖Ωk∥22+∥(xp−xS+rp)Ωk∖S∥22≤2∥(xp−xS+rp)W∥2.(14)\begin{aligned} \lVert(u^p-x_S)_{(S\cup Q^p)\setminus\Omega_k}\rVert_2 &\le\lVert(x^p-x_S+r^p)_{(S\cup Q^p)\setminus\Omega_k}\rVert_2+\lVert(x^p-x_S+r^p)_{\Omega_k\setminus S}\rVert_2\\ &\le\sqrt{2}\sqrt{\lVert(x^p-x_S+r^p)_{(S\cup Q^p)\setminus\Omega_k}\rVert_2^2+\lVert(x^p-x_S+r^p)_{\Omega_k\setminus S}\rVert_2^2}\\ &\le\sqrt{2}\lVert(x^p-x_S+r^p)_W\rVert_2. \tag*{(14)} \end{aligned}

where the last inequality results from ((S∪Qp)∖Ωk)∪(Ωk∖S)⊆W\left((S\cup Q^p)\setminus\Omega_k\right)\cup(\Omega_k\setminus S)\subseteq W and ((S∪Qp)∖Ωk)∩(Ωk∖S)=∅\left((S\cup Q^p)\setminus\Omega_k\right)\cap(\Omega_k\setminus S)=\varnothing. Since y=Ax+νy=Ax+\nu, we have

rp=AT(y−Axp)=AT[A(xS−xp)+ν′],(15)r^p=A^{T}(y-Ax^p)=A^{T}\left[A(x_S-x^p)+\nu'\right], \tag*{(15)}

where ν′=ν+AxS‾\nu'=\nu+Ax_{\overline{S}}. Since supp⁡(xp−xS)⊆W\operatorname{supp}(x^p-x_S)\subseteq W and ∣W∣≤3k|W|\leq3k, from (15) and Lemma 2.2, we obtain

∥(xp−xS+rp)W∥2=∥[(I−ATA)(xp−xS)+ATν′]W∥2≤∥[(I−ATA)(xp−xS)]W∥2+∥(ATν′)W∥2≤δ3k∥xp−xS∥2+1+δ3k∥ν′∥2.(16)\begin{aligned} \left\|\left(x^p-x_S+r^p\right)_W\right\|_2 &=\left\|\left[(I-A^TA)(x^p-x_S)+A^T\nu'\right]_W\right\|_2\\ &\leq\left\|\left[(I-A^TA)(x^p-x_S)\right]_W\right\|_2+\left\|(A^T\nu')_W\right\|_2\\ &\leq\delta_{3k}\|x^p-x_S\|_2+\sqrt{1+\delta_{3k}}\|\nu'\|_2. \tag*{(16)} \end{aligned}

Combining (14) and (16), we get

∥(up−xS)(S∪Qp)∖Ωk∥2≤2δ3k∥xp−xS∥2+2(1+δ3k)∥ν′∥2.(17)\left\|\left(u^p-x_S\right)_{(S\cup Q^p)\setminus\Omega_k}\right\|_2 \leq\sqrt{2}\delta_{3k}\|x^p-x_S\|_2+\sqrt{2(1+\delta_{3k})}\|\nu'\|_2. \tag*{(17)}

Secondly, we estimate the upper bound of ∥(up−xS)Ωk∥2\|(u^p-x_S)_{\Omega_k}\|_2. From (4), (5) and (15), we obtain

(up−xS)Ωk=(xp−xS)Ωk+αMp(rp)Ωk=(xp−xS)Ωk+αMpAΩkT[A(xS−xp)+ν′]=(xp−xS)Ωk+αMpAΩkT[A(S∪Qp)∖Ωk(xS−xp)(S∪Qp)∖Ωk+AΩk(xS−xp)Ωk+ν′]=(1−α)(xp−xS)Ωk+αMp[AΩkTA(S∪Qp)∖Ωk(xS−xp)(S∪Qp)∖Ωk+AΩkTν′].(18)\begin{aligned} (u^p-x_S)_{\Omega_k} &=(x^p-x_S)_{\Omega_k}+\alpha M^p(r^p)_{\Omega_k}\\ &=(x^p-x_S)_{\Omega_k}+\alpha M^p A_{\Omega_k}^{T}\left[A(x_S-x^p)+\nu'\right]\\ &=(x^p-x_S)_{\Omega_k}+\alpha M^p A_{\Omega_k}^{T}\left[A_{(S\cup Q^p)\setminus\Omega_k}(x_S-x^p)_{(S\cup Q^p)\setminus\Omega_k}+A_{\Omega_k}(x_S-x^p)_{\Omega_k}+\nu'\right]\\ &=(1-\alpha)(x^p-x_S)_{\Omega_k}+\alpha M^p\left[A_{\Omega_k}^{T}A_{(S\cup Q^p)\setminus\Omega_k}(x_S-x^p)_{(S\cup Q^p)\setminus\Omega_k}+A_{\Omega_k}^{T}\nu'\right]. \tag*{(18)} \end{aligned}

where the third equality is given by supp⁡(xS−xp)⊆W\operatorname{supp}(x_S-x^p)\subseteq W and W=[(S∪Qp)∖Ωk]∪ΩkW=[(S\cup Q^p)\setminus\Omega_k]\cup\Omega_k. Since Ωk∩[(S∪Qp)∖Ωk]=∅\Omega_k\cap[(S\cup Q^p)\setminus\Omega_k]=\varnothing, thus AΩkTA(S∪Qp)∖ΩkA_{\Omega_k}^{T}A_{(S\cup Q^p)\setminus\Omega_k} is a submatrix of AWTAW−IA_W^TA_W-I. Hence,

∥AΩkTA(S∪Qp)∖Ωk∥2≤∥AWTAW−I∥2≤δ3k,(19)\left\|A_{\Omega_k}^{T}A_{(S\cup Q^p)\setminus\Omega_k}\right\|_2 \leq\left\|A_W^TA_W-I\right\|_2\leq\delta_{3k}, \tag*{(19)}

where the last inequality results from Definition 2.1 with ∣W∣≤3k|W|\leq3k. From Definition 2.1, the eigenvalues of AΩkTAΩkA_{\Omega_k}^{T}A_{\Omega_k} lie in [1−δk,1+δk][1-\delta_k,1+\delta_k], and thus those of Mp=(AΩkTAΩk)−1M^p=(A_{\Omega_k}^{T}A_{\Omega_k})^{-1} belong to [11+δk,11−δk]\left[\frac{1}{1+\delta_k},\frac{1}{1-\delta_k}\right]. Hence, ∥Mp∥2≤11−δk\|M^p\|_2\leq\frac{1}{1-\delta_k}. Combining this bound with (18) and (19), we arrive at

∥(up−xS)Ωk∥2≤∣1−α∣⋅∥(xp−xS)Ωk∥2+α∥Mp∥2(∥AΩkTA(S∪Qp)∖Ωk∥2⋅∥(xp−xS)(S∪Qp)∖Ωk∥2+∥AΩkTν′∥2)≤∣1−α∣⋅∥(xp−xS)Ωk∥2+α1−δk(δ3k∥(xp−xS)(S∪Qp)∖Ωk∥2+∥(ATν′)Ωk∥2)≤∣1−α∣⋅∥xp−xS∥2+α1−δk(δ3k∥(up−xS)(S∪Qp)∖Ωk∥2+1+δ3k∥ν′∥2).(20)\begin{aligned} \|(u^p-x_S)_{\Omega_k}\|_2 &\leq|1-\alpha|\cdot\|(x^p-x_S)_{\Omega_k}\|_2+\alpha\|M^p\|_2\left(\|A_{\Omega_k}^{T}A_{(S\cup Q^p)\setminus\Omega_k}\|_2\cdot\|(x^p-x_S)_{(S\cup Q^p)\setminus\Omega_k}\|_2+\|A_{\Omega_k}^{T}\nu'\|_2\right)\\ &\leq|1-\alpha|\cdot\|(x^p-x_S)_{\Omega_k}\|_2+\frac{\alpha}{1-\delta_k}\left(\delta_{3k}\|(x^p-x_S)_{(S\cup Q^p)\setminus\Omega_k}\|_2+\|(A^T\nu')_{\Omega_k}\|_2\right)\\ &\leq|1-\alpha|\cdot\|x^p-x_S\|_2+\frac{\alpha}{1-\delta_k}\left(\delta_{3k}\|(u^p-x_S)_{(S\cup Q^p)\setminus\Omega_k}\|_2+\sqrt{1+\delta_{3k}}\|\nu'\|_2\right). \tag*{(20)} \end{aligned}

where the last inequality is obtained by the first equality of (12) and Lemma 2.2 with ∣Ωk∣<3k|\Omega_k|<3k. For a,b∈R2a,b\in\mathbb{R}^2 and ξ,η≥0\xi,\eta\geq0, the following inequality holds:

∑i=12(aiξ+biη)2=∥a∥22ξ2+∥b∥22η2+2⟨a,b⟩ξη≤(∥a∥2ξ+∥b∥2η)2,(21)\sum_{i=1}^{2}(a_i\xi+b_i\eta)^2=\|a\|_2^2\xi^2+\|b\|_2^2\eta^2+2\langle a,b\rangle\xi\eta\leq(\|a\|_2\xi+\|b\|_2\eta)^2, \tag*{(21)}

where the last inequality results form ∣⟨a,b⟩∣≤∥a∥2∥b∥2|\langle a,b\rangle|\leq\|a\|_2\|b\|_2. Combining (20) and (21), we find

∥(up−xS)W∥2=∥(up−xS)Ωk∥22+∥(up−xS)(S∪Qp)∖Ωk∥22≤C4∥(up−xS)(S∪Qp)∖Ωk∥2+∣1−α∣⋅∥xp−xS∥2+α1+δ3k1−δk∥ν′∥2.\begin{aligned} \|(u^p-x_S)_W\|_2 &=\sqrt{\|(u^p-x_S)_{\Omega_k}\|_2^2+\|(u^p-x_S)_{(S\cup Q^p)\setminus\Omega_k}\|_2^2}\\ &\leq C_4\|(u^p-x_S)_{(S\cup Q^p)\setminus\Omega_k}\|_2+|1-\alpha|\cdot\|x^p-x_S\|_2+\frac{\alpha\sqrt{1+\delta_{3k}}}{1-\delta_k}\|\nu'\|_2. \end{aligned}

where C4C_4 is given in Theorem 3.2. It follows from (17) that

∥(up−xS)W∥2≤(∣1−α∣+2δ3kC4)⋅∥xp−xS∥2+(2C4+α1−δk)1+δ3k⋅∥ν′∥2.(22)\|(u^p-x_S)_W\|_2\leq\left(|1-\alpha|+\sqrt{2}\delta_{3k}C_4\right)\cdot\|x^p-x_S\|_2+\left(\sqrt{2}C_4+\frac{\alpha}{1-\delta_k}\right)\sqrt{1+\delta_{3k}}\cdot\|\nu'\|_2. \tag*{(22)}

Substituting (22) into (11), we get

∥xp+1−xS∥2≤ρ∥xp−xS∥2+[1+δ3k1−δ2k2(2C4+2α1−δk)+1+δk1−δ2k]∥ν′∥2≤ρ∥xp−xS∥2+C∥ν′∥2,(23)\|x^{p+1}-x_S\|_2\leq\rho\|x^p-x_S\|_2+\left[\frac{\sqrt{1+\delta_{3k}}}{\sqrt{1-\delta_{2k}^2}}\left(2C_4+\frac{\sqrt{2}\alpha}{1-\delta_k}\right)+\frac{\sqrt{1+\delta_k}}{1-\delta_{2k}}\right]\|\nu'\|_2\leq\rho\|x^p-x_S\|_2+C\|\nu'\|_2, \tag*{(23)}

where ρ\rho, CC are given in (10) and the last inequality is given by δ2k≤δ3k\delta_{2k}\leq\delta_{3k}. It means that (9) holds.

Finally, we prove that ρ<1\rho<1 under the conditions in (7). Denote F(r):=2r1−r2(r1−r)2+1F(r):=\frac{2r}{\sqrt{1-r^2}}\sqrt{\left(\frac{r}{1-r}\right)^2+1}, r∈[0,1)r\in[0,1). Since F(r)F(r) is strictly increasing on [0,1)[0,1), it follows from (8) and (7) that

C3C1=F(δ3k)≤F(320)<1,\frac{C_3}{C_1}=F(\delta_{3k})\leq F\left(\sqrt{\frac{3}{20}}\right)<1,

where the last inequality is easily verified and thus omitted. Hence, C3<C1<1C_3<C_1<1, which implies that the second inequality in (7) is well defined. Since δk≤δ2k≤δ3k\delta_k \le\delta_{2k} \le\delta_{3k}, (10) implies that

ρ≤21−δ3k2(∣1−α∣+2δ3k(αδ3k1−δ3k)2+1)=1C1(∣1−α∣+2δ3kα2C22+1),(24)\rho\le\frac{\sqrt{2}}{\sqrt{1-\delta_{3k}^{2}}}\left(\lvert1-\alpha\rvert+\sqrt{2}\delta_{3k}\sqrt{\left(\frac{\alpha\delta_{3k}}{1-\delta_{3k}}\right)^{2}+1}\right)=\frac{1}{C_{1}}\left(\lvert1-\alpha\rvert+\sqrt{2}\delta_{3k}\sqrt{\alpha^{2}C_{2}^{2}+1}\right), \tag*{(24)}

where the equality is given by (8). It is easy to check that the following inequality

α2t2+1≤{1+(1+t2−1)α,0<α≤1,tα+1+t2−t,α>1,(25)\sqrt{\alpha^{2}t^{2}+1}\le\begin{cases}1+\left(\sqrt{1+t^{2}}-1\right)\alpha, & 0<\alpha\le1,\\ t\alpha+\sqrt{1+t^{2}}-t, & \alpha>1,\end{cases} \tag*{(25)}

holds for any t≥0t\ge0. Combining (24) and (25) with t=C2t=C_{2} leads to

ρ≤1C1{1−α+2δ3k[1+(1+C22−1)α],0<α≤1,α−1+2δ3k(C2α+1+C22−C2),α>1,=1C1{(1+2δ3k−C3)(1−α)+C3,0<α≤1,(2δ3kC2+1)(α−1)+C3,α>1,\begin{aligned} \rho\le\frac{1}{C_{1}}\begin{cases}1-\alpha+\sqrt{2}\delta_{3k}\left[1+\left(\sqrt{1+C_{2}^{2}}-1\right)\alpha\right], & 0<\alpha\le1,\\ \alpha-1+\sqrt{2}\delta_{3k}\left(C_{2}\alpha+\sqrt{1+C_{2}^{2}}-C_{2}\right), & \alpha>1,\end{cases} \\ &=\frac{1}{C_{1}}\begin{cases}\left(1+\sqrt{2}\delta_{3k}-C_{3}\right)(1-\alpha)+C_{3}, & 0<\alpha\le1,\\ \left(\sqrt{2}\delta_{3k}C_{2}+1\right)(\alpha-1)+C_{3}, & \alpha>1,\end{cases} \end{aligned}

where the equality is given by the definition of C3C_{3} in (8). It follows from (7) that ρ<1\rho<1. □

The global convergence of SDSNT follows directly from Theorem 3.2 under certain conditions; see Remark 3.3.

Remark 3.3. If xx is a kk-sparse vector and its measurement vector yy is accurate, i.e., xS=xx_{S}=x and ν=0\nu=0, then (9) reduces to ∥xp+1−x∥2≤ρ∥xp−x∥2\lVert x^{p+1}-x\rVert_{2}\le\rho\lVert x^{p}-x\rVert_{2}, where ρ<1\rho<1 is given by (10). Consequently, the iterates {xp}\{x^{p}\} generated by SDSNT converges to xx.

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 nn and the number of measurements mm are fixed at n=10000n=10000 and m=3000m=3000. The measurement matrix A∈Rm×nA\in\mathbb{R}^{m\times n} is randomly generated, and its elements are sampled independently from N(0,1m)\mathcal{N}\left(0,\frac{1}{m}\right).

Recovery of random sparse vector

We first evaluate the recovery performance of the algorithms on 100 random instances for each sparsity level kk, ranging from 600 to 1500 with stepsize 20. For each instance, the noisy measurements y∈Rmy\in\mathbb{R}^{m} of a kk-sparse vector x∗∈Rnx^{*}\in\mathbb{R}^{n} are generated by y=Ax∗+εhy=Ax^{*}+\varepsilon h, where h∈Rmh\in\mathbb{R}^{m} is a normalized Gaussian noise vector and ε=0.01\varepsilon=0.01. The nonzero positions of x∗x^{*} are uniformly distributed, with values drawn independently from N(0,1)\mathcal{N}(0,1). We aim to recover x∗x^{*} from the data (y,A)(y,A), and a recovery is deemed successful if the solution xpx^{p} produced by an algorithm satisfies ∥xp−x∗∥2/∥x∗∥2≤10−3\lVert x^{p}-x^{*}\rVert_{2}/\lVert x^{*}\rVert_{2}\le10^{-3}, 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 k≤840k \le840, SDSNT exhibits lower computational cost than NHTP; however, when kk increases beyond this threshold, its average CPU time gradually surpasses that of NHTP. A similar pattern holds for NTP with k≤980k \le980. The above results reveal that SDSNT achieves superior computational efficiency at low sparsity levels.

Success rates and average CPU times of the algorithms

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 z^∈Rn\hat{z} \in\mathbb{R}^{n} depicted in Figure 2(b). This signal is transformed into a compressible vector x^∈Rn\hat{x} \in\mathbb{R}^{n} via the orthogonal transform W=W2∘W1\mathbf{W} = \mathbf{W}_{2} \circ\mathbf{W}_{1}, i.e., x^=Wz^\hat{x} = \mathbf{W}\hat{z}. Here, W1\mathbf{W}_{1} stands for the discrete cosine transform, and W2\mathbf{W}_{2} denotes the three-level discrete wavelet transform based on the ‘sym12’ wavelet with periodic extension. Given measurements y=(AW)z^∈Rmy = (\mathbf{A}\mathbf{W})\hat{z} \in\mathbb{R}^{m} of the signal z^\hat{z}, we reconstruct a kk-sparse vector x~∈Rn\tilde{x} \in\mathbb{R}^{n} from the data (y,A)(y,\mathbf{A}) using an algorithm with k=m/3k = m/3, where x~\tilde{x} is the best kk-term approximation of x^\hat{x}. Consequently, the reconstructed signal z~\tilde{z} is given by z~=W−1x~\tilde{z} = \mathbf{W}^{-1}\tilde{x}. We use the signal-to-noise ratio (SNR), defined by SNR:=20log⁡10(∥z^∥2/∥z^−z~∥2)\mathrm{SNR} := 20\log_{10}(\lVert\hat{z}\rVert_{2}/\lVert\hat{z}-\tilde{z}\rVert_{2}), 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.

Comparison of SNR versus CPU time and original audio signal versus reconstructed 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. [1]T. Blumensath, M.E. Davies, Iterative thresholding for sparse approximations, J. Fourier Anal. Appl. 14 (2008) 629–654.DOI
  2. [2]E.J. Candès, T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51(12) (2005) 4203–4215.DOI
  3. [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. [4]S. Foucart, Hard thresholding pursuit: An algorithm for compressive sensing, SIAM J. Numer. Anal. 49 (6) (2011) 2543–2563.DOI
  5. [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. [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. [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. [8]J. Nocedal, S.J. Wright, Numerical Optimization, Springer, New York, 2006.
  9. [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. [10]Y. Ye, Q. Li, Subspace Newton’s method for ℓ₀-regularized optimization problems with box constraints, J. Sci. Comput. 106 (2026) 68.DOI
  11. [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. [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.

Paper details

vlnc:W_2snq8dvk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents