# Expander OMP Sparse Inference

- ID: 345
- Canonical URL: https://synthcore.org/idea/345/expander-omp-sparse-inference
- API JSON: https://synthcore.org/api/idea/345.json
- API Markdown: https://synthcore.org/api/idea/345.md
- Verification status: mechanism_failed
- Source: [arXiv:2607.01799](https://arxiv.org/abs/2607.01799)
- Category: architecture
- Solves: speedup, memory, scalability
- ML areas: inference-speedup, embedding, memory, retrieval
- Math tags: linear-algebra, combinatorics, sparse-recovery
- Ratings: usefulness 6/10; difficulty 4/10; novelty 6/10

## Idea description

Use the expander decoder as a structured sparse-coding dictionary and replace dense OMP correlation steps with edge-wise gather-and-reduce operations. This is useful when codes must be inferred iteratively, including interpretable feature extraction, sparse retrieval, or an inference-time latent selector that cannot rely entirely on an amortized encoder.

## Mathematical statement

Orthogonal Matching Pursuit maintains a residual r^(t) = h - W x^(t) and selects the feature with the largest dictionary correlation. For a dense dictionary, the correlation vector is c^(t) = W transpose r^(t), costing O(mn). With W = A elementwise-multiplied by Theta and exactly d active coordinates per column, each correlation is c_j^(t) = sum over i with A_ij = 1 of w_ij r_i^(t), so all correlations require O(dn) multiply-adds and gathers. OMP selects j_t = argmax over unselected j of |c_j^(t)|, enlarges the support S, and refits coefficients by least squares on the selected columns. The residual is then recomputed as r^(t+1) = h - W_S x_S. Expansion of neighborhoods for sets up to 2k reduces support collisions, while column normalization makes correlation magnitudes comparable.

## Key formulas

- $$\mathbf{c}^{(t)}=\mathbf{W}^{\top}\mathbf{r}^{(t)},\qquad j_t=\arg\max_{j\notin S_t}|c_j^{(t)}|$$
- $$c_j^{(t)}=\sum_{i:A_{ij}=1}w_{ij}r_i^{(t)},\qquad \operatorname{cost}(\mathbf{c}^{(t)})=O(dn)$$
- $$S_{t+1}=S_t\cup\{j_t\},\qquad \mathbf{x}_{S_{t+1}}=\arg\min_{u}\|\mathbf{h}-\mathbf{W}_{S_{t+1}}u\|_2^2$$
- $$\mathbf{r}^{(t+1)}=\mathbf{h}-\mathbf{W}_{S_{t+1}}\mathbf{x}_{S_{t+1}}$$

## Implementation notes

(1) Integration point: implement an inference-only sparse encoder for a frozen dictionary, or use it as a teacher that generates sparse targets for a learned amortized encoder. Store the dictionary as edge arrays row[e], col[e], and weight[e] for e from 1 to dn. (2) Pseudocode: set residual R = H, support S_b = empty, and coefficient matrix X = zero for each batch item b. For t from 0 to k minus 1, initialize correlations C = zero; for each edge e, gather R[:, row[e]], multiply by weight[e], and reduce into C[:, col[e]]. Set selected columns to negative infinity, choose j_t as the maximum absolute correlation, and append it to the support. Form W_S from the selected columns, solve x_S = (W_S transpose W_S + lambda I)^(-1) W_S transpose h, and update R = H - W_S x_S. (3) The mathematical contribution is the O(dn) correlation formula and OMP support/refit recursion. Estimate speed from actual fused gather-reduce kernels; lambda, batching, and stopping thresholds are engineering choices. (4) First experiment: use 10,000 Pythia-70M residual vectors and compare dense batched OMP, expander OMP, and the amortized TopK encoder. Measure latency, peak memory, reconstruction error versus iteration count, and support overlap with dense OMP. Success is a substantial correlation-time reduction with comparable MSE at k selected features; report the break-even point where sparse-kernel overhead dominates.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built dense and edge-wise OMP using fixed-degree sparse dictionaries stored as edge arrays. The core correlation identity was verified to floating-point precision (maximum error 4.4e-16), and both OMP implementations produced identical supports, coefficients, and reconstruction MSE (9.58e-5). However, the transparent unfused edge gather-reduce was slower than optimized dense BLAS by 1.8x–163x in the tested sizes, so the intended speedup was not observed; a fused kernel is needed for a fair systems-level test.

### Mechanism check

- Verdict: Built dense and edge-wise OMP using fixed-degree sparse dictionaries stored as edge arrays. The core correlation identity was verified to floating-point precision (maximum error 4.4e-16), and both OMP implementations produced identical supports, coefficients, and reconstruction MSE (9.58e-5). However, the transparent unfused edge gather-reduce was slower than optimized dense BLAS by 1.8x–163x in the tested sizes, so the intended speedup was not observed; a fused kernel is needed for a fair systems-level test.
- Confidence: 9/10
- Limitations: Only synthetic CPU experiments were run. The edge reduction is a Python loop rather than a fused CUDA or compiled scatter-reduce kernel; no Pythia residuals, amortized TopK encoder, GPU benchmark, peak-memory measurement, or large-scale end-to-end inference test was performed.

## Artifacts

- [expander_omp.py](https://synthcore.org/code/1269/expander_omp.py)
- [report.md](https://synthcore.org/code/1269/report.md)
- [results.json](https://synthcore.org/code/1269/results.json)
- [Download all files as ZIP](https://synthcore.org/download/1269)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.