What does Sparse Probes, Hidden Discounts conclude, in numbers, about “Rounding, Anniversary Coupons and Hold-Out Quotes: from Exact to Stable Recovery”?

Answer: Chapter 5 handles rounding, anniversary coupons and threshold rules: with rounding to ten fen the equality model is mostly infeasible, while the robust model still finds every support with a worst error of 0.03 yuan, and only 0.0403 of wrong tables pass one hold-out quote.

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.03

n = 100, k = 5, m = 30, 20 trials per row
quantum qnoise sdequality LP infeasiblesupport rightworst
0.010.00290 of 2020 of 200.00
0.100.028919 of 2020 of 200.03
1.000.288719 of 2020 of 200.39
5.001.443419 of 208 of 2011.37
Show the full program
# Chapter 5. p51: rounded totals - from exact recovery to stable recovery.
# Model: n = 100 items, k = 5 hidden discounts that are percentages of
# shelf price (so not whole yuan: 3.20 to 48.60 yuan), m = 30 basket
# quotes whose totals are rounded to a quantum q (0.01, 0.1, 1 or 5
# yuan). Rounding error is uniform on [-q/2, q/2], standard deviation
# q / sqrt(12). Equality basis pursuit can become infeasible, so we
# solve min sum x + sum |e| subject to A x + e = y, x >= 0 (an LP with
# e = e+ - e-), drop cells below 2 q and refit the kept cells by least
# squares. 20 seeded trials per row (seed 20261151); 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


rng = random.Random(20261151)
n, k, m, T = 100, 5, 30, 20
print("n = %d, k = %d, m = %d, %d trials per row" % (n, k, m, T))
print("quantum q  noise sd  equality LP infeasible  support right"
      "  worst")
for q in (0.01, 0.1, 1.0, 5.0):
    right, worst, infeas = 0, 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.0] * n
        for j in rng.sample(range(n), k):
            x[j] = round(rng.uniform(3.2, 48.6), 2)
        y = [round(math.fsum(A[i][j] * x[j] for j in range(n)) / q) * q
             for i in range(m)]
        xe, _, _ = lp_min(A, y, [1] * n)
        infeas += xe is None
        AE = [A[i] + [1 if t == i else 0 for t in range(m)]
              + [-1 if t == i else 0 for t in range(m)]
              for i in range(m)]
        xb, _, _ = lp_min(AE, y, [1] * (n + 2 * m))
        keep = [j for j in range(n) if xb[j] > 2 * q]
        cols = [[A[i][j] for i in range(m)] for j in keep]
        G = [[dot(a, b) for b in cols] for a in cols]
        coef = solve(G, [dot(a, y) for a in cols]) if keep else []
        xr = [0.0] * n
        for t, j in enumerate(keep):
            xr[j] = coef[t]
        sup = sorted(j for j in range(n) if x[j])
        right += keep == sup
        worst = max(worst, max(abs(xr[j] - x[j]) for j in range(n)))
    print("%9.2f  %8.4f  %15d of %d  %10d of %d  %5.2f"
          % (q, q / math.sqrt(12), infeas, T, right, T, worst))

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 5: Rounding, Anniversary Coupons and Hold-Out Quotes: from Exact to Stable 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