An eigenvalue decomposition based method is developed that formally guarantees recovery of all sparse solutions if there is more than one and two optimization-based methods achieving favorable computational complexity are developed.
Abstract
We consider the problem of finding sparse solutions of an underdetermined linear system $Ax=b$. In contrast to conventional approaches based on greedy algorithms or convex relaxation, we reformulate sparse approximation as a structured system of polynomial equations and connect with the literature on tensor methods. We develop an eigenvalue decomposition based method that formally guarantees recovery of all sparse solutions if there is more than one. We also develop two optimization-based methods achieving favorable computational complexity. The new methods allow explicit control of the target sparsity. Numerical experiments illustrate the performance and compare to basis pursuit (denoising) and orthogonal matching pursuit.
This paper considers the local convergence for solving general nonlinear equations. We establish randomized quasi-Gauss--Newton methods based on the approximation of the Gram matrix, addressing both the underdetermined and the overdetermined settings. For the underdetermined case, we show that our methods achieve local...
In order to solve large sparse linear systems, we introduce a relaxation factor into the iterative formula based on the randomized Kaczmarz method. According to this idea, a parameterized randomized Kaczmarz method is constructed. Then, the convergence of this method is proved when the linear systems are consistent. Nu...
Chen-Xiao Gao, Fang Chen· Journal of Mathematical Stud...· 0 citations
We study a class of weakly convex optimization problems in which the objective is the sum of a smooth convex term and a weakly convex term that may be non-smooth. To exploit this structure, we develop a splitting technique based on the alternating direction method of multipliers (ADMM), which decouples the minimization...
Sheng-Han Mei, Cheng-Yu Ke, Yifei Lou et al.· Frontiers in Applied Mathema...· 0 citations
This paper studies the minimization of a bi-quadratic function with a linear term. As both a quartic programming problem and a generalized convex multiplicative programming problem, it poses significant challenges for standard convex optimization methods. We propose an adaptive branch-and-bound algorithmic framework ba...
We analyze two fixed-point iterations for computing the principal square root of an M-matrix $A$. Although these iterations, with customary initialization, converge sublinearly when $A$ is a singular M-matrix, we show that, under suitable mild conditions on the initial approximation, the convergence is linear. Moreover...
D. Bini, B. Iannazzo, B. Meini et al.· 0 citations
