Papers › A Fast Interior Point Method for Atomic Norm Soft Thresholding
A Fast Interior Point Method for Atomic Norm Soft Thresholding
Thomas Lundgaard Hansen, Tobias Lindstrøm Jensen
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
The atomic norm provides a generalization of the ℓ₁-norm to continuous parameter spaces. When applied as a sparse regularizer for line spectral estimation the solution can be obtained by solving a convex optimization problem. This problem is known as atomic norm soft thresholding (AST). It can be cast as a semidefinite program and solved by standard methods. In the semidefinite formulation there are O(N²) dual variables which complicates the implementation of a standard primal-dual interior-point method based on symmetric cones. That has lead researcher to consider alternating direction method of multipliers (ADMM) for the solution of AST, but this method is still somewhat slow for large problem sizes. To obtain a faster algorithm we reformulate AST as a non-symmetric conic program. That has two properties of key importance to its numerical solution: the conic formulation has only O(N) dual variables and the Toeplitz structure inherent to AST is preserved. Based on it we derive FastAST which is a primal-dual interior point method for solving AST. Two variants are considered with the fastest one requiring only O(N²) flops per iteration. Extensive numerical experiments demonstrate that FastAST solves AST significantly faster than a state-of-the-art solver based on ADMM.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections