Recovering sparse DFT from missing signals via interior point method on GPU
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916601058557952 |
|---|---|
| author | Kuang, Wei Montoison, Alexis Rao, Vishwas Pacaud, François Anitescu, Mihai |
| author_facet | Kuang, Wei Montoison, Alexis Rao, Vishwas Pacaud, François Anitescu, Mihai |
| contents | We propose a method to recover the sparse discrete Fourier transform (DFT) of a signal that is both noisy and potentially incomplete, with missing values. The problem is formulated as a penalized least-squares minimization based on the inverse discrete Fourier transform (IDFT) with an $\ell_1$-penalty term, reformulated to be solvable using a primal-dual interior point method (IPM). Although Krylov methods are not typically used to solve Karush-Kuhn-Tucker (KKT) systems arising in IPMs due to their ill-conditioning, we employ a tailored preconditioner and establish new asymptotic bounds on the condition number of preconditioned KKT matrices. Thanks to this dedicated preconditioner -- and the fact that FFT and IFFT operate as linear operators without requiring explicit matrix materialization -- KKT systems can be solved efficiently at large scales in a matrix-free manner. Numerical results from a Julia implementation leveraging GPU-accelerated interior point methods, Krylov methods, and FFT toolkits demonstrate the scalability of our approach on problems with hundreds of millions of variables, inclusive of real data obtained from the diffuse scattering from a slightly disordered Molybdenum Vanadium Dioxide crystal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04217 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Recovering sparse DFT from missing signals via interior point method on GPU Kuang, Wei Montoison, Alexis Rao, Vishwas Pacaud, François Anitescu, Mihai Optimization and Control We propose a method to recover the sparse discrete Fourier transform (DFT) of a signal that is both noisy and potentially incomplete, with missing values. The problem is formulated as a penalized least-squares minimization based on the inverse discrete Fourier transform (IDFT) with an $\ell_1$-penalty term, reformulated to be solvable using a primal-dual interior point method (IPM). Although Krylov methods are not typically used to solve Karush-Kuhn-Tucker (KKT) systems arising in IPMs due to their ill-conditioning, we employ a tailored preconditioner and establish new asymptotic bounds on the condition number of preconditioned KKT matrices. Thanks to this dedicated preconditioner -- and the fact that FFT and IFFT operate as linear operators without requiring explicit matrix materialization -- KKT systems can be solved efficiently at large scales in a matrix-free manner. Numerical results from a Julia implementation leveraging GPU-accelerated interior point methods, Krylov methods, and FFT toolkits demonstrate the scalability of our approach on problems with hundreds of millions of variables, inclusive of real data obtained from the diffuse scattering from a slightly disordered Molybdenum Vanadium Dioxide crystal. |
| title | Recovering sparse DFT from missing signals via interior point method on GPU |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2502.04217 |