Optimization for Compressed Sensing: the Simplex Method and Kronecker Sparsification
In this paper we present two new approaches to efficiently solve large-scale compressed sensing problems. These two ideas are independent of each other and can therefore be used either separately or together. We consider all possibilities. For the first approach, we note that the zero vector can be taken as the initial basic (infeasible) solution for the linear programming problem and therefore, if the true signal is very sparse, some variants of the simplex method can be expected to take only a small number of pivots to arrive at a solution. We implemented one such variant and demonstrate a dramatic improvement in computation time on very sparse signals. The second approach requires a redesigned sensing mechanism in which the vector signal is stacked into a matrix. This allows us to exploit the Kronecker compressed sensing (KCS) mechanism. We show that the Kronecker sensing requires stronger conditions for perfect recovery compared to the original vector problem. However, the Kronecker sensing, modeled correctly, is a much sparser linear optimization problem. Hence, algorithms that benefit from sparse problem representation, such as interior-point methods, can solve the Kronecker sensing problems much faster than the corresponding vector problem. In our numerical studies, we demonstrate a ten-fold improvement in the computation time.
Code (0)
등록된 구현이 없습니다.
Tasks
compressed sensingSimilar Papers 제목 키워드 기반
A Hierarchical View of Structured Sparsity in Kronecker Compressive Sensing
Kronecker compressed sensing refers to using Kronecker product matrices as sparsifying bases and measurement matrices in compressed sensing. This work focuses on the Kronecker compressed sensing problem, encompassing thr…
compressed sensingCompressive SensingMethods for Sparse and Low-Rank Recovery under Simplex Constraints
The de-facto standard approach of promoting sparsity by means of $\ell_1$-regularization becomes ineffective in the presence of simplex constraints, i.e.,~the target is known to have non-negative entries summing up to a …
compressed sensingDensity EstimationPortfolio OptimizationQuantum State TomographyPhysics-guided Deep Unfolding Network for Enhanced Kronecker Compressive sensing
Deep networks have achieved remarkable success in image compressed sensing (CS) task, namely reconstructing a high-fidelity image from its compressed measurement. However, existing works are deficient inincoherent compre…
Compressive SensingGradient Sparsification Can Improve Performance of Differentially-Private Convex Machine Learning
We use gradient sparsification to reduce the adverse effect of differential privacy noise on performance of private machine learning models. To this aim, we employ compressed sensing and additive Laplace noise to evaluat…
BIG-bench Machine Learningcompressed sensingPrivacy PreservingOver-the-Air Federated Learning with Compressed Sensing: Is Sparsification Necessary?
Over-the-Air (OtA) Federated Learning (FL) refers to an FL system where multiple agents apply OtA computation for transmitting model updates to a common edge server. Two important features of OtA computation, namely line…
compressed sensingFederated Learning