What does Sparse Probes, Hidden Discounts conclude, in numbers, about “No Full Census Needed: Basket Quotes, Sparse Hidden Discounts and Exact L1 Recovery”?
Answer: Chapter 1 checks and corrects the sources of the founding claim and uses an exact simplex method in fractions to recover 3 hidden discounts among 40 items from 12 basket quotes, while least squares smears them over the whole table with a worst cell error of 26.73 yuan; it measures the scheduling constant, with the quote share falling to 0.0825 of the item count.
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: 12, 26.73, 40
| cells n | 40, hidden discounts k = 3, basket quotes m = 12 |
| full census | 40 single-item quotes |
| basket sizes | 25 15 21 20 13 19 19 22 15 24 14 15 |
| discount totals y | 30 0 30 18 0 35 12 47 35 65 35 12 |
| cell true L1 (exact) min-L2 | |
| 7 | 18 18 5.49 |
| 21 | 35 35 8.27 |
| 33 | 12 12 3.12 |
| L1 equals truth in all 40 cells, as fractions: True | |
| L1 nonzero cells | 3 |
| min-L2 nonzero cells | 40, cells off by 1 yuan or more: 31 |
| min-L2 worst cell error | 26.73 yuan |
| simplex pivots (exact, Bland's rule) | 50 |
| first q quotes only, exact? 3:n 4:n 5:n 6:n 7:n 8:n 9:n 10:Y 11:Y 12:Y |
Key formula
Show the full program
# Chapter 1. p11: 12 basket quotes recover 3 hidden discounts among 40.
# Model: a competitor lists n = 40 items at public shelf prices; under
# one public checkout condition, k = 3 items carry a hidden discount
# (whole yuan). A probe is a basket quote that shows only the total;
# shelf total minus quoted total = sum of hidden discounts in the
# basket, so y = A x with A a 0/1 basket matrix. We compare basis
# pursuit (min sum x, A x = y, x >= 0; exact simplex in fractions)
# with the minimum-L2 answer x = A'(AA')^-1 y. Illustrative numbers;
# baskets are drawn with a fixed seed, each item in with chance 1/2.
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_exact(G, h):
k = len(G)
M = [list(G[i]) + [h[i]] for i in range(k)]
for c in range(k):
p = next(i for i in range(c, k) if M[i][c] != 0)
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)]
n, m = 40, 12
truth = {7: 18, 21: 35, 33: 12}
x = [truth.get(j, 0) for j in range(n)]
rng = random.Random(20261113)
A = [[1 if rng.random() < 0.5 else 0 for _ in range(n)]
for _ in range(m)]
y = [int(math.fsum(A[i][j] * x[j] for j in range(n))) for i in range(m)]
xb, lam, piv = lp_min(A, y, [1] * n, exact=True)
G = [[Fr(esum([Fr(A[p][j] * A[q][j]) for j in range(n)]))
for q in range(m)] for p in range(m)]
mu = solve_exact(G, [Fr(v) for v in y])
x2 = [esum([A[i][j] * mu[i] for i in range(m)]) for j in range(n)]
err2 = [abs(float(x2[j]) - x[j]) for j in range(n)]
print("cells n = %d, hidden discounts k = %d, basket quotes m = %d"
% (n, len(truth), m))
print("full census: %d single-item quotes" % n)
print("basket sizes: %s" % " ".join(str(int(math.fsum(r))) for r in A))
print("discount totals y: %s" % " ".join(str(v) for v in y))
print("cell true L1 (exact) min-L2")
for j in sorted(truth):
print("%4d %4d %10s %6.2f" % (j, x[j], xb[j], float(x2[j])))
print("L1 equals truth in all %d cells, as fractions: %s"
% (n, xb == [Fr(v) for v in x]))
print("L1 nonzero cells: %d" % len([v for v in xb if v != 0]))
print("min-L2 nonzero cells: %d, cells off by 1 yuan or more: %d"
% (len([v for v in x2 if v != 0]),
len([e for e in err2 if e >= 1])))
print("min-L2 worst cell error: %.2f yuan" % max(err2))
print("simplex pivots (exact, Bland's rule): %d" % piv)
row = []
for mm in range(3, m + 1):
xs, _, _ = lp_min(A[:mm], y[:mm], [1] * n, exact=True)
row.append("%d:%s" % (mm, "Y" if xs == [Fr(v) for v in x] else "n"))
print("first q quotes only, exact? " + " ".join(row))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 1: No Full Census Needed: Basket Quotes, Sparse Hidden Discounts and Exact L1 Recovery. 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 2 · L1 as a Linear Program: the Two-Phase Simplex, Dual Certificates and a Design Check for Probes
- 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