What does Sparse Probes, Hidden Discounts conclude, in numbers, about “The Price of Greed: Orthogonal Matching Pursuit, Coherence and Worst-Case Guarantees”?
Answer: Chapter 3 compares orthogonal matching pursuit: on one hundred items L1 reaches ninety percent success with 22 quotes, nonnegative OMP with 26 and plain OMP with 34, while worst-case coherence guarantees are nearly useless.
Scope of the numbers: Its items, amounts, costs and rivals are illustrative and all calculations are generated by its programs; it is a general business reference, not a legal opinion. Marked boxes separate published evidence, runnable Python calculations (18 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 22, 26, 34
| n | 100, k = 5, 20 trials per row |
| m BP OMP NN-OMP | |
| 14 | 4 0 2 |
| 18 | 13 1 9 |
| 22 | 19 9 16 |
| 26 | 20 16 19 |
| 30 | 20 16 20 |
| 34 | 20 20 20 |
| 38 | 20 20 20 |
| BP first reaches 18 of 20 at m | 22 |
| OMP first reaches 18 of 20 at m | 34 |
| NN-OMP first reaches 18 of 20 at m | 26 |
| k ln(n/k) | 14.98; m/(k ln(n/k)) at BP's mark = 1.47 |
Show the full program
# Chapter 3. p32: basis pursuit against greedy pursuit, 20 trials each.
# Model: n = 100 items, k = 5 hidden discounts of 5 to 60 yuan, m basket
# quotes with each item in with chance 1/2. Every trial uses the same
# draw for all three methods (common random numbers). Success means
# every rounded cell equals the truth. Seed 20261131; illustrative.
import math
import random
from fractions import Fraction as Fr
def esum(v):
s = Fr(0)
for t in v:
s += t
return s
def lp_min(A, b, c, exact=False):
# min c.x subject to A x = b, x >= 0: two-phase tableau simplex.
# b is nudged to b + A d (d_j > 0, tiny, distinct) so that no
# pivot is degenerate; the final basis is re-applied to the true
# b through B^-1. Exact mode uses fractions and Bland's rule.
m, n = len(A), len(A[0])
cv = Fr if exact else float
add = esum if exact else math.fsum
tol = 0 if exact else 1e-9
big = 1 + max(abs(v) for v in b)
d = [Fr(1, 2 ** (30 + j)) if exact else
1e-7 * big * (0.5 + (0.6180339887 * (j + 1)) % 1.0)
for j in range(n)]
T, sg = [], []
for i in range(m):
s = -1 if b[i] < 0 else 1
row = [cv(s * v) for v in A[i]] + [cv(0)] * (m + 1)
row[n + i] = cv(1)
row[-1] = cv(abs(b[i])) + s * add([A[i][j] * d[j]
for j in range(n)])
T.append(row)
sg.append(s)
basis = [n + i for i in range(m)]
W = n + m
def pivot(r, q, z):
pv = T[r][q]
T[r] = [v / pv for v in T[r]]
pr = T[r]
nz = [j for j in range(W + 1) if pr[j] != 0]
for row in T + [z]:
f = row[q]
if row is not pr and f != 0:
for j in nz:
row[j] -= f * pr[j]
basis[r] = q
def run(z, stop):
piv = 0
while not (stop and -z[W] <= tol):
q, best = -1, -1e-7
for j in range(n):
if exact and z[j] < 0:
q = j
break
if not exact and z[j] < best:
q, best = j, z[j]
if q < 0:
return piv
r, rt = -1, None
for i in range(m):
if T[i][q] > tol:
t = T[i][W] / T[i][q]
if rt is None or t < rt:
r, rt = i, t
pivot(r, q, z)
piv += 1
return piv
z = [cv(0)] * (W + 1)
for j in list(range(n)) + [W]:
z[j] = -add([T[i][j] for i in range(m)])
piv = run(z, True)
if -z[W] > (0 if exact else 1e-6 * big):
return None, None, piv
z = [cv(v) for v in c] + [cv(0)] * (m + 1)
for i in range(m):
if basis[i] < n and z[basis[i]] != 0:
f = z[basis[i]]
z = [z[j] - f * T[i][j] for j in range(W + 1)]
piv += run(z, False)
x = [cv(0)] * n
for i in range(m):
if basis[i] < n:
x[basis[i]] = add([T[i][n + j] * abs(b[j])
for j in range(m)])
lam = [-sg[j] * z[n + j] for j in range(m)]
return x, lam, piv
def solve(G, h):
# Gauss-Jordan with partial pivoting for a small square system
k = len(G)
M = [list(G[i]) + [h[i]] for i in range(k)]
for c in range(k):
p = max(range(c, k), key=lambda i: abs(M[i][c]))
M[c], M[p] = M[p], M[c]
for i in range(k):
if i != c and M[i][c] != 0:
f = M[i][c] / M[c][c]
M[i] = [M[i][j] - f * M[c][j] for j in range(k + 1)]
return [M[i][k] / M[i][i] for i in range(k)]
def dot(a, b):
return math.fsum(u * v for u, v in zip(a, b))
def omp(A, y, kmax, tol=1e-6, nonneg=False):
# orthogonal matching pursuit: pick the column most correlated
# with the residual, refit by least squares on the chosen set
m, n = len(A), len(A[0])
cols = [[float(A[i][j]) for i in range(m)] for j in range(n)]
nr = [math.sqrt(dot(c, c)) or 1.0 for c in cols]
r, S, coef = [float(v) for v in y], [], []
while len(S) < kmax and math.sqrt(dot(r, r)) > tol:
best, jb = None, -1
for j in range(n):
if j not in S:
g = dot(cols[j], r) / nr[j]
g = g if nonneg else abs(g)
if best is None or g > best:
best, jb = g, j
S.append(jb)
G = [[dot(cols[p], cols[q]) for q in S] for p in S]
coef = solve(G, [dot(cols[p], y) for p in S])
r = [y[i] - math.fsum(coef[t] * cols[S[t]][i]
for t in range(len(S)))
for i in range(m)]
x = [0.0] * n
for t, j in enumerate(S):
x[j] = coef[t]
return x, S
n, k, T = 100, 5, 20
rng = random.Random(20261131)
print("n = %d, k = %d, %d trials per row" % (n, k, T))
print(" m BP OMP NN-OMP")
first = {}
for m in range(14, 39, 4):
hits = [0, 0, 0]
for _ in range(T):
A = [[1 if rng.random() < 0.5 else 0 for _ in range(n)]
for _ in range(m)]
x = [0] * n
for j in rng.sample(range(n), k):
x[j] = rng.randint(5, 60)
y = [int(math.fsum(A[i][j] * x[j] for j in range(n)))
for i in range(m)]
xb, _, _ = lp_min(A, y, [1] * n)
xo, _ = omp(A, y, m)
xp, _ = omp(A, y, m, nonneg=True)
for t, v in enumerate((xb, xo, xp)):
if v is not None and [round(u) for u in v] == x:
hits[t] += 1
for t in range(3):
if hits[t] >= 0.9 * T and t not in first:
first[t] = m
print("%3d %3d %3d %6d" % (m, hits[0], hits[1], hits[2]))
names = ("BP", "OMP", "NN-OMP")
for t in range(3):
print("%-6s first reaches 18 of 20 at m = %s"
% (names[t], first.get(t, "beyond 38")))
print("k ln(n/k) = %.2f; m/(k ln(n/k)) at BP's mark = %.2f"
% (k * math.log(n / k), first.get(0, 0) / (k * math.log(n / k))))Single source and citation
Fan, Y. (2026). Compressed Sensing and L1 Minimisation: Sparse Mystery-Shopper Probes and the Exact Recovery of Competitors' Hidden-Discount Matrices (Version 1.0.0), Chapter 3: The Price of Greed: Orthogonal Matching Pursuit, Coherence and Worst-Case Guarantees. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-242 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026242,
author = {Fan, Yafu},
title = {Compressed Sensing and L1 Minimisation: Sparse Mystery-Shopper Probes and the Exact Recovery of Competitors' Hidden-Discount Matrices},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · No Full Census Needed: Basket Quotes, Sparse Hidden Discounts and Exact L1 Recovery
- Chapter 2 · L1 as a Linear Program: the Two-Phase Simplex, Dual Certificates and a Design Check for Probes
- Chapter 4 · The Phase Diagram: Probe Share, Sparsity and the Value of Knowing the Sign
- Chapter 5 · Rounding, Anniversary Coupons and Hold-Out Quotes: from Exact to Stable Recovery
- Chapter 6 · The Hidden-Discount Matrix: Joint Sparsity across Public Conditions, and Basket Size
- Chapter 7 · Classical Sources East and West: Foreknowledge in Sunzi's "Use of Spies" and Shannon's Count of Samples
- Chapter 8 · Closing the Loop: a Monthly Mystery-Shopper Probe Schedule, a Compliance Checklist and a Pre-Registered Test