Splitting Alternating Algorithms for Sparse Solutions of Linear Systems with Concatenated Orthogonal Matrices

Yun-Bin Zhao, Zhong-Feng Sun · 2025

Read Splitting Alternating Algorithms for Sparse Solutions of Linear Systems with Concatenated Orthogonal Matrices by Yun-Bin Zhao, Zhong-Feng Sun (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-24558.txt.

Introduction

Finding the sparsest solution to a linear system is faster when the system splits into small orthogonal blocks. Yun-Bin Zhao and Zhong-Feng Sun propose a class of splitting alternating algorithms for systems whose matrix joins several orthogonal blocks side by side. Two-block and multi-block versions divide the big system into coupled subsystems, solve each, and recombine the answers.

The steps need only matrix-vector products and reduced projections. Under a coherence-type condition on the matrix and the sparsity level, the methods converge globally to the sparse solution. In experiments they located sparse solutions in far fewer iterations than mainstream iterative methods, with high accuracy.

Catalog record

CREATORYun-Bin Zhao, Zhong-Feng Sun
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-24558

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Splitting Alternating Algorithms for Sparse Solutions of Linear Systems with Concatenated Orthogonal Matrices Thanks: Submitted to the editors November 2, 2024. Yun-Bin Zhao, Zhong-Feng Sun Abstract A class of splitting alternating algorithms is proposed for finding the sparse solution of linear systems with concatenated orthogonal matrices. Depending on the number of matrices concatenated, the proposed algorithms are classified into the two-block splitting alternating algorithm (TSAA) and the multi-block splitting alternating algorithm (MSAA). These algorithms aim to decompose a large-scale linear system into two or more coupled subsystems, each significantly smaller than the original system, and then combine the solutions of these subsystems to produce the sparse solution of the original system. The proposed algorithms only involve matrix-vector products and reduced orthogonal projections. It turns out that the proposed algorithms are globally convergent to the sparse solution of a linear system if the matrix (along with the sparsity level of the solution) satisfies a coherence-type condition. Numerical experiments indicate that the proposed algorithms are very promising and can quickly and accurately locate the sparse solution of a linear system with significantly fewer iterations than several mainstream iterative methods. se counter=example]example[2][]title=Example \thetcbcounter : #2,#1 keywords Sparse solutions of linear systems, concatenated orthogonal matrices, splitting alternating algorithms, mutual coherence, hard thresholding, signal and image reconstruction Funding. This work was supported by the National Key Research and Development Program of China (2023YFA1009302), National Natural Science Foundation of China (12471295, 12426306, 12071307, 12371305), Guangdong Basic and Applied Basic Research Foundation (2024A1515011566), and the Hetao Shenzhen-Hong Kong Science and Technology Innovation Cooperation Zone Project (HZQSWS-KCCYB-2024016). † † runningheads: Splitting Alternating Algorithms / Yun-Bin Zhao and Zhong-Feng Sun MSC 65F10, 94A12, 15A29, 65H10, 49M27 1 Introduction The sparse solution of an underdetermined linear system has gained significant interest in the field of science and engineering [ 6 , 17 , 21 , 50 , 1 , 32 ] . Many practical problems can be formulated as finding the sparse solution to a linear system, which commonly arises in compressive sampling [ 7 , 13 ] , signal and image reconstruction [ 17 , 35 , 34 , 1 ] , linear inverse problem [ 3 , 42 , 45 , 43 ] , model selection [ 28 , 24 ] , and wireless network [ 11 , 33 ] . The fundamental model for the sparse solution of a linear system can be cast as \min\{\|x\|_{0}:~y=Ax\}, (1) where y\in\mathbb{R}^{m} is a given vector, A is a given m\times n matrix with m\ll n, and \|x\|_{0} counts the number of nonzero entries of x\in\mathbb{R}^{n}. The data pair (y,A) may have different interpretations depending on application context. For instance, in compressive sampling [ 7 , 13 ] , A is referred to as the measurement matrix and the entries of y are the acquired measurements of the signal; in wireless communication [ 11 , 33 ] , A is called the channel-gain matrix, and the entries of y are the received signals at the terminals. Before proceeding, let us review some existing algorithms developed over the past decades for solving ( 1 ). (i) Convex optimization methods . Problem ( 1 ) can often be well approximated by the \ell_{1} -minimization model \min\{\|x\|_{1}:y=Ax\} which is a convex optimization model (see, e.g., [ 10 , 8 ] ). The Lasso model \min\{\|y-Ax\|_{2}^{2}+\lambda\|x\|_{1}\}, where \lambda is a positive parameter, is also a popular convex approximation of ( 1 ) [ 5 , 2 , 28 ] . Replacing \|x\|_{0} in ( 1 ) with a nonconvex ‘merit function for sparsity’ and employing a linearization technique, one can develop the reweighted \ell_{1} -minimization methods for this problem [ 9 , 52 , 50 ] . Additionally, the so-called dual-density-based approach in [ 54 , 50 ] is also a convex optimization method for this problem. Convex optimization problems are typically solved using interior-point methods which are efficient for reasonably sized problems but have a significantly higher computational cost compared to the next two classes of methods. (ii) OMP-type methods. The orthogonal matching pursuit (OMP) was introduced in the statistics literature several decades ago and later extended to signal processing [ 40 , 36 , 47 , 17 ] . Although OMP performs well for ( 1 ) in many cases, it is relatively slow in locating the high-sparsity-level solution of large-scale problems. This is because the total number of iterations required by OMP is at least equal to the number of nonzero entries in the solution. This issue also affects the variants of OMP, including the stagewise orthogonal matching pursuit [ 15 ] and weak orthogonal matching pursuit [ 46 ] . (iii) Thresholding-type methods. The iterative hard thresholding (IHT) [ 4 ] and hard thresholding pursuit (HTP) [ 20 ] are also popular methods for solving ( 1 ). Combining matching pursuit [ 36 ] with hard thresholding gives rise to the compressive sampling matching pursuit (CoSaMP) [ 39 ] and subspace pursuit (SP) [ 12 ] . Soft-thresholding methods, including the iterative shrinkage-thresholding algorithms (ISTA) and fast iterative shrinkage-thresholding algorithm (FISTA) [ 3 ] , are also widely used for finding sparse solutions of linear systems. However, it is known that IHT, ISTA, and FISTA converge slowly and their performance is sensitive to the choice of parameters such as stepsize or soft-thresholding parameter. Recent developments in thresholding-type methods can be found in [ 44 , 22 , 51 , 37 , 27 , 45 , 29 , 31 , 16 ] . Problem ( 1 ) is NP-hard [ 38 ] and developing an efficient general-purpose algorithm for it is challenging. The aim of this paper is to develop an efficient, customized algorithm for a class of structured large-scale problems involving matrices that are concatenations of orthogonal matrices: A=[\Phi_{1},\Phi_{2},\cdots,\Phi_{p}], (2) where \Phi_{i}, i=1,\dots,p are m\times m orthogonal matrices. Such matrices have long been used as measurement matrices in signal and image recovery [ 14 , 18 , 17 , 19 , 26 ] , and they appear in applications like distributed compressed sensing and distributed sensor networks [ 30 , 41 , 48 ] . Concatenated orthogonal matrices have both theoretical and practical advantages due to their reduced coherence, which is crucial for robust signal recovery [ 17 , 26 , 30 ] . However, the existing methods such as \ell_{1} -minimization, OMP and thresholding methods use the matrix as a whole, failing to exploit its internal structure. Compressive sampling theory [ 8 , 17 , 21 ] indicates that the performance of a signal-reconstruction algorithm is closely tied to the structure of the measurement matrix and its properties such as reduced coherence [ 17 ] , restricted isometry property [ 8 ] , null space property [ 21 ] , and range space property [ 50 ] . Both simulations and practical applications demonstrate that the matrix structure significantly impacts the performance of signal processing algorithms. Therefore, it is essential to develop an algorithm that fully leverages the matrix structure while maintaining low computational cost for solving large-scale problems. In this paper, we develop the splitting alternating algorithms (SAA) for finding sparse solutions to large-scale linear systems with concatenated orthogonal matrices. When two matrices are concatenated, the algorithm is

Read the complete text