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 n40, hidden discounts k = 3, basket quotes m = 12
full census40 single-item quotes
basket sizes25 15 21 20 13 19 19 22 15 24 14 15
discount totals y30 0 30 18 0 35 12 47 35 65 35 12
cell true L1 (exact) min-L2
718 18 5.49
2135 35 8.27
3312 12 3.12
L1 equals truth in all 40 cells, as fractions: True
L1 nonzero cells3
min-L2 nonzero cells40, cells off by 1 yuan or more: 31
min-L2 worst cell error26.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

\[y = \sum_{j \in \text{basket}} p_j - T = \sum_{j \in \text{basket}} x_j .\]
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