Precision as a Coherence Budget: Co-Designing Sensing Matrices and Low-Bit Sparse Recovery Hardware

Many physical sensors produce measurements in which the unknown signal is a sparse combination of nearly identical "atoms." Adjacent projector rows in a 3D scanner look almost the same, and neighbouring beam directions in a phased-array radio look almost the same. Recovering which atoms are present means telling apart inner products that differ only in their last few significant digits. Solvers that cope with this similarity, such as norm-ratio minimization and Sparse Bayesian Learning, have so far been studied only in double-precision software. The hardware that would make them real-time works in the opposite regime. Photonic cores, in-memory crossbars and microcontrollers get their efficiency from 8-bit arithmetic and tolerate a few percent of analog noise. This note proposes to treat arithmetic precision and sensing-matrix similarity as one shared budget. The more similar the atoms, the more bits the recovery datapath needs. Designing the sensing matrix for lower similarity buys back bits, and therefore energy.

The concrete claim is that the bits a sparse-recovery datapath needs grow roughly like the logarithm of $1/(1-\mu)$ plus the logarithm of the signal's internal dynamic range. Here $\mu$ is the mutual coherence, the largest normalized inner product between two columns of the sensing matrix. A second claim is that scale-invariant objectives such as $\ell_1/\ell_2$ allow a cheap hardware trick that removes the global-scale part of the problem entirely. If both claims hold, the right design question changes from "which matrix has the lowest coherence?" to "which pair of matrix and bit allocation reaches a target recovery rate at the lowest energy?" We will build and test that joint design.

Core Claim

A back-of-envelope argument gives the shape of the claim. Consider two unit-norm atoms with correlation $\mu$. Suppose a greedy or proximal step must decide between them, and the residual carries a true component of size $x_{\min}$. The gap between the two correlation scores is about $(1-\mu)\,x_{\min}$. A uniform quantizer with $b$ bits over a full-scale range set by the largest coefficient $x_{\max}$ adds errors of order $2^{-b}x_{\max}$. Resolving the gap therefore needs

$$ b \;\gtrsim\; \log_2\frac{1}{1-\mu} \;+\; \log_2\frac{x_{\max}}{x_{\min}} \;+\; c, $$

where $c$ absorbs accumulation length and noise. This is a hypothesis to be measured, not a theorem. It says three things. Coherence and within-signal dynamic range cost bits additively. Overall signal scale should cost nothing. And at the coherence levels where norm-ratio solvers are reported to win, uniform 8-bit hardware is likely to fail. Those levels include the oversampled DCT at factor $F=20$ in Accelerated Schemes for the $L_1/L_2$ Minimization.

Nobody has measured this. Wang et al. show that $\ell_1/\ell_2$ is robust to signals whose nonzeros differ by $10^3$ to $10^5$. A spread of $10^5$ alone is about 17 bits by the formula above, which already exceeds the 8-bit budget of ENLighten before coherence is counted. This conflict motivates the project.

What Is New Relative to the Closest Work

Three lines of work each touch part of this question, and they divide neatly. The first line designs the sensing matrix under hardware rules. Koller and Utschick learn constant-modulus phase-shifter matrices by matching compressed channel vectors to a uniform distribution on a sphere, which avoids the coherence spikes of random matrices. Anjarlekar and Rajwade design binary micromirror patterns with weighted bi- and tri-coherence penalties. Both treat the reconstruction solver as ideal floating-point software.

The second line builds solvers that tolerate coherence. These include the $\ell_1/\ell_2$ adaptive schemes, the squared-ratio $\tau_2$ model with its Dinkelbach-based D-LPMM solver in Sparse Recovery: The Square of ℓ1/ℓ2 Norms, and Sparse Bayesian Learning. Sparse Bayesian Learning models each coefficient as Gaussian with its own learned variance. It is used for multi-path correction in Sparse Multi-Path Corrections in Fringe Projection Profilometry and is unrolled into a recurrent network (GFLSTM) in From Bayesian Sparsity to Gated Recurrent Nets. None of this work considers finite precision.

The third line is hardware-software co-design. ENLighten aligns structured sparsity with photonic core granularity under 8-bit, 3%-noise conditions. AQPIM quantizes activations inside memory. Both target feedforward networks, not ill-conditioned inverse problems.

Our proposal differs from all three. It makes precision an explicit term coupling matrix design to solver hardware. It exploits a property specific to norm-ratio objectives, scale invariance, as a hardware feature. And it searches the matrix, solver and bit allocation jointly.

Research Program

The first component is a bit-accurate measurement study. We will port five solvers to a fixed-point emulator with configurable per-operation word lengths: Lasso, OMP, $\ell_1/\ell_2$-A2, $\tau_2$ D-LPMM, and Sparse Bayesian Learning together with its unrolled GFLSTM form. The operations are matrix-vector products, Gram updates, proximal steps and accumulators. The emulator will also offer an analog mode with multiplicative noise at the 3% level used by ENLighten. For each solver we sweep coherence and within-signal dynamic range, then record the smallest word length that keeps support-recovery success within one point of the double-precision rate. Coherence is swept through the DCT oversampling factor $F$ and through phase-shifter resolution in the mmWave model. Fitting the slope of required bits against $\log_2 1/(1-\mu)$ and against $\log_2$ dynamic range tests the core formula directly.

The second component is the scale-invariance trick. The $\ell_1/\ell_2$ and $\tau_2$ objectives do not change when $x$ is multiplied by a constant. A solver can therefore renormalize its iterate to the full range of the fixed-point format at every iteration. It keeps a single shared exponent and rescales the measurement vector $b$ consistently, so the constraint stays exact. The cost is one extra register.

This is block floating point justified by the objective, not by heuristics. Convex $\ell_1$ with a fixed regularization weight does not admit it. We expect it to remove the overall-scale part of the bit requirement, so that only coherence and within-signal spread remain.

The third component is joint design. The sensing matrix is parameterized by its physical controls: phase angles quantized to the phase shifter's bit depth, or binary mirror states. We optimize the matrix against the Koller–Utschick MMD loss plus a precision-aware penalty. The penalty is a smooth surrogate of the bit requirement above, computed over the column pairs and triples flagged by weighted bi-coherence.

An outer search then chooses the solver, the per-operation word lengths and the matrix. The objective is energy from an operation-count and memory-access cost model, subject to a recovery-rate constraint. In the analog setting we instead train the unrolled GFLSTM with injected quantization and analog noise. The cost model is analytical. For the matrix-vector kernels we will check it against synthesized FPGA designs, because the gap between simulated and real hardware flagged in the co-design literature, for example around DAMOV, is a real risk.

Baselines

The naive reference point is each solver taken unchanged and run with uniform 8-bit fixed-point arithmetic, with the matrix designed for floating point. This is what a sequential workflow would deliver: design the algorithm first, then let a standard quantizer deploy it. Our joint design must beat it by a clear margin in recovery rate at equal energy. Otherwise precision is not the binding constraint and the project's premise fails. The double-precision version of every solver is reported alongside as the ceiling.

The strongest competitor on the matrix side is the MMD-learned constant-modulus matrix of Koller and Utschick. They report that it matches with 64 measurements the estimation accuracy a random matrix needs 96 for, a 33% reduction in receiver chains on a realistic 5-path mmWave channel. We will reimplement it on that channel model, quantize it to the same phase-shifter resolution as ours, and pair it with the same solver and bit budget. Beating it means one of two outcomes at matched energy and matched optimizer budget. Either our matrix reaches the same channel-estimation error with fewer datapath bits, or it reaches the same error with fewer measurements below 64 at 8 bits. On the binary side, weighted bi-coherence matrices from Anjarlekar and Rajwade serve the same role on Berkeley image patches. That paper reports gains in structural similarity (SSIM) but no single headline value in the file, so the comparison will be run fresh.

The strongest competitor on the solver side is GFLSTM, which reportedly cuts Photometric Stereo reconstruction on the Caesar data from about 90 s with classical Sparse Bayesian Learning to about 2 s. It also reaches near-100% strict support accuracy on correlated dictionaries where $\ell_1$ and ISTA-Net fail. We will retrain it with quantization-aware training at the same bit widths, on the same online synthetic data generator and with the same tuning budget as our variants. We found no reported result on Lacuna for any coherence-resilient solver under fixed-point or analog execution. All low-precision baselines are therefore our own runs.

Two ablations isolate the key ingredients. The first removes per-iteration scale renormalization from the norm-ratio solvers. If the claimed overall-scale saving is real, required bits should rise by roughly $\log_2$ of the overall-scale range. The second removes the precision-aware penalty from matrix design, leaving MMD or bi-coherence alone. This ablation is exactly the sequential "design the matrix, then quantize" pipeline, and the gap it leaves is the co-design dividend.

Why not just…?

Why not just run the solvers in 32-bit floating point on a GPU? For offline work this is fine, and our double-precision ceiling covers it. The question is the energy and latency regime of embedded sensing. Examples are the sub-100 KB microcontroller budgets in the wearable co-design study and the real-time scanning that the fringe-projection authors say needs dedicated hardware. Our cost model reports energy at 32, 16 and 8 bits. If 16-bit floating point fits every target budget, this alternative wins and we will say so.

Why not just apply quantization-aware training to the unrolled GFLSTM? This is the most serious threat, because training with noise might absorb the precision loss with no change to the matrix. It is included as a full baseline. It has a known weakness, though: the network is tied to one fixed dictionary, as its authors acknowledge. So it cannot exploit a redesigned matrix without retraining, and it cannot provide the scale-invariance guarantee. If quantization-aware GFLSTM on the floating-point-designed matrix matches our joint design, the precision-aware matrix term is unnecessary and we would narrow the claim to the solver side.

Why not just add measurements instead of bits? More rows lower effective coherence, and Koller and Utschick show measurement count and matrix quality trade against each other. We treat this as an axis, not an objection. The joint search reports the full measurements-by-bits frontier. The proposal stands only if spending design effort on the matrix moves that frontier, not just a point along it.

Proposed Experiments

The first decisive check is the slope test on the oversampled DCT benchmark. For $F$ from 2 to 20 and dynamic ranges from $10^0$ to $10^5$, we measure the minimum word length for each solver. The formula predicts roughly one extra bit per halving of $1-\mu$ and per doubling of dynamic range. It also predicts a near-zero overall-scale term once renormalization is on. A flat or erratic slope would mean coherence does not govern precision, and the joint objective would lose its basis.

The second check is the mmWave 5-path channel. We compare channel-estimation error against energy for random, MMD and joint matrices, crossed with 4- to 8-bit datapaths and 2- to 6-bit phase shifters.

The third check uses fringe-projection multi-path simulations, scored by Chamfer distance over 500 trials as in the original work. These test whether constrained Sparse Bayesian Learning and its unrolled form keep their advantage over OMP and Lasso at 8 bits with 3% analog noise. They also test whether the roughly 17-path separation ceiling found by singular-value analysis shrinks as precision falls, which the formula predicts because the decaying singular values behave like extra coherence.

Finally, FPGA synthesis of the matrix-vector and proximal kernels for the winning configurations will confirm that the cost model ranks designs correctly. If it does not, energy claims will be restated in measured hardware terms.