# ORKA: Accelerated Kaczmarz Algorithms for Signal Recovery from One-Bit Samples

arXiv: https://arxiv.org/abs/2301.03467 · HTML: https://mlsanity.com/paper/2301.03467/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 63 references that are in the map.
- First posted on arXiv 8 Dec 2022.

## Builds on (most cited first, 7 of 7)

- [On Unlimited Sampling and Reconstruction](https://mlsanity.com/paper/1905.03901/) (2019)
- [A Sampling Kaczmarz-Motzkin Algorithm for Linear Feasibility](https://mlsanity.com/paper/1605.01418/) (2016)
- [Sampling Kaczmarz Motzkin Method for Linear Feasibility Problems: Generalization & Acceleration](https://mlsanity.com/paper/2002.07321/) (2020)
- [A Survey on Matrix Completion: Perspective of Signal Processing](https://mlsanity.com/paper/1901.10885/) (2019)
- [One-Bit Phase Retrieval: More Samples Means Less Complexity?](https://mlsanity.com/paper/2203.08982/) (2022)
- [On the Randomized Kaczmarz Algorithm](https://mlsanity.com/paper/1402.2863/) (2014)
- [Gridless Parameter Estimation for One-Bit MIMO Radar with Time-Varying Thresholds](https://mlsanity.com/paper/1908.10487/) (2019)

## Built on by (most cited first, 1 of 1)

- [One-Bit Quadratic Compressed Sensing: From Sample Abundance to Linear Feasibility](https://mlsanity.com/paper/2303.09594/) (2023)

## Abstract (arXiv)

One-bit quantization with time-varying sampling thresholds has recently found significant utilization potential in statistical signal processing applications due to its relatively low power consumption and low implementation cost. In addition to such advantages, an attractive feature of one-bit analog-to-digital converters (ADCs) is their superior sampling rates as compared to their conventional multi-bit counterparts. This characteristic endows one-bit signal processing frameworks with what we refer to as sample abundance. On the other hand, many signal recovery and optimization problems are formulated as (possibly non-convex) quadratic programs with linear feasibility constraints in the one-bit sampling regime. We demonstrate, with a particular focus on the nuclear norm minimization, that the sample abundance paradigm allows for the transformation of such quadratic problems to merely a linear feasibility problem by forming a large-scale overdetermined linear system; thus removing the need for costly optimization constraints and objectives. To make this achievable, we propose enhanced randomized Kaczmarz algorithms to tackle these highly overdetermined feasibility problems. Several numerical results are presented to illustrate the effectiveness of the proposed methodologies.