What does Sparse Probes, Hidden Discounts conclude, in numbers, about “L1 as a Linear Program: the Two-Phase Simplex, Dual Certificates and a Design Check for Probes”?
Answer: Chapter 2 writes L1 as a two-phase simplex, treats degeneracy and perturbation, issues certificates of uniqueness, and gives a design check for baskets: zero and identical columns pull the recovery share of three-cell supports from 0.969 to 0.704.
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: 0.704, 0.969
| clean design: zero columns [], identical pairs [] | |
| k | 1: 20 of 20 exact (1.000); failures on 5/12/17: 0 of 0 |
| k | 2: 190 of 190 exact (1.000); failures on 5/12/17: 0 of 0 |
| k | 3: 1105 of 1140 exact (0.969); failures on 5/12/17: 12 of 35 |
| flawed design: zero columns [17], identical pairs [(5, 12)] | |
| k | 1: 18 of 20 exact (0.900); failures on 5/12/17: 2 of 2 |
| k | 2: 153 of 190 exact (0.805); failures on 5/12/17: 37 of 37 |
| k | 3: 802 of 1140 exact (0.704); failures on 5/12/17: 327 of 338 |
Show the full program
# Chapter 2. p22: audit a basket design before anyone goes shopping.
# Model: n = 20 items, m = 10 basket quotes, each item in a basket with
# chance 1/2 (seeded), then two planted flaws seen in real plans: item
# 12 always rides with item 5 (identical columns) and item 17 is never
# put in any basket (zero column). For nonnegative basis pursuit the
# outcome depends only on which cells are nonzero, so we test every
# support of size 1, 2 and 3 with x = 1 there (1,350 linear programs,
# float simplex) and count the supports recovered exactly.
import itertools
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 audit(A, n, k):
good, bad = 0, []
for S in itertools.combinations(range(n), k):
y = [len([j for j in S if A[i][j]]) for i in range(len(A))]
xh, _, _ = lp_min(A, y, [1] * n)
x = [1 if j in S else 0 for j in range(n)]
if xh is not None and max(abs(a - b)
for a, b in zip(xh, x)) < 1e-6:
good += 1
else:
bad.append(S)
return good, bad
n, m = 20, 10
rng = random.Random(20261122)
A = [[1 if rng.random() < 0.5 else 0 for _ in range(n)]
for _ in range(m)]
clean = [r[:] for r in A]
for r in A:
r[12] = r[5]
r[17] = 0
for name, D in (("clean design", clean), ("flawed design", A)):
cols = [tuple(D[i][j] for i in range(m)) for j in range(n)]
zero = [j for j in range(n) if not any(cols[j])]
twins = [(a, b) for a, b in itertools.combinations(range(n), 2)
if cols[a] == cols[b]]
print("%s: zero columns %s, identical pairs %s"
% (name, zero, twins))
for k in (1, 2, 3):
good, bad = audit(D, n, k)
tot = math.comb(n, k)
hit = len([S for S in bad if 17 in S or (5 in S) != (12 in S)
or (5 in S and 12 in S)])
print(" k = %d: %4d of %4d exact (%.3f); failures on"
" 5/12/17: %d of %d"
% (k, good, tot, good / tot, hit, len(bad)))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 2: L1 as a Linear Program: the Two-Phase Simplex, Dual Certificates and a Design Check for Probes. 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 3 · The Price of Greed: Orthogonal Matching Pursuit, Coherence and Worst-Case Guarantees
- 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