What does Sparse Probes, Hidden Discounts conclude, in numbers, about “The Hidden-Discount Matrix: Joint Sparsity across Public Conditions, and Basket Size”?

Answer: Discounts under several public conditions form a matrix side by side, and the discounted items are largely the same across conditions; this is joint sparsity. Program p61 showed that joint information lets the greedy SOMP clearly beat column-wise OMP, but that on nonnegative zero-one baskets column-wise L1 is still the best: from 24 quotes on the whole matrix is always right, 96 quotes over 4 conditions against 320 for a full census. Program p62 showed that basket size carries costs at both ends: with 2 items per basket it takes 78 quotes, more than a full census; from 15 items upward 16 quotes suffice, but the items handled grow as baskets grow. With this the mathematical part is complete. The next chapter returns to two classical sources: Sunzi, who held that foreknowledge "must be obtained from people", and Shannon, who held that a signal is completely determined by its samples. What did they get right, and where do today's data rewrite them?

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: 15, 16, 24, 320, 96

n = 80 items, L = 4 conditions, k = 6 discounted items
mOMP per columnSOMP jointBP per columnquotes
120/200/203/2048
162/201/2011/2064
202/205/2018/2080
249/2015/2020/2096
2815/2020/2020/20112
3218/2020/2020/20128
full census of the matrix: 320 single-item quotes
Show the full program
# Chapter 6. p61: the hidden-discount matrix - one support, four columns.
# Model: n = 80 items x L = 4 public checkout conditions. Hidden
# discounts sit on the same k = 6 items across conditions (row
# sparsity); each of those items is discounted under each condition
# with chance 0.7, by 5 to 60 yuan. The same m baskets are quoted under
# every condition, so Y = A X. We compare OMP and basis pursuit run
# column by column with simultaneous OMP (Tropp, Gilbert and Strauss
# 2006), which picks the item that best explains all four residuals at
# once and refits every column on the shared support. Success = the
# whole 80 x 4 matrix exact. 20 seeded trials per row (seed 20261161).
# 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


def somp(A, Y, kmax, tol=1e-6):
    m, n, L = len(A), len(A[0]), len(Y)
    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 = [[float(v) for v in y] for y in Y]
    S, X = [], [[0.0] * n for _ in range(L)]
    while len(S) < kmax and max(dot(r, r) for r in R) > tol:
        sc = [-1.0 if j in S else
              math.fsum(abs(dot(cols[j], r)) for r in R) / nr[j]
              for j in range(n)]
        S.append(max(range(n), key=lambda j: sc[j]))
        G = [[dot(cols[p], cols[q]) for q in S] for p in S]
        for l in range(L):
            coef = solve(G, [dot(cols[p], Y[l]) for p in S])
            X[l] = [0.0] * n
            for t, j in enumerate(S):
                X[l][j] = coef[t]
            R[l] = [Y[l][i] - math.fsum(coef[t] * cols[S[t]][i]
                                        for t in range(len(S)))
                    for i in range(m)]
    return X


rng = random.Random(20261161)
n, L, k, T = 80, 4, 6, 20
print("n = %d items, L = %d conditions, k = %d discounted items"
      % (n, L, k))
print("  m   OMP per column   SOMP joint   BP per column   quotes")
for m in range(12, 33, 4):
    hb = hs = ho = 0
    for _ in range(T):
        A = [[1 if rng.random() < 0.5 else 0 for _ in range(n)]
             for _ in range(m)]
        rows = rng.sample(range(n), k)
        X = [[0] * n for _ in range(L)]
        for j in rows:
            for l in range(L):
                if rng.random() < 0.7:
                    X[l][j] = rng.randint(5, 60)
        Y = [[int(math.fsum(A[i][j] * X[l][j] for j in range(n)))
              for i in range(m)] for l in range(L)]
        ho += all([round(v) for v in omp(A, Y[l], m)[0]] == X[l]
                  for l in range(L))
        good = True
        for l in range(L):
            xb, _, _ = lp_min(A, Y[l], [1] * n)
            good = good and [round(v) for v in xb] == X[l]
        hb += good
        XS = somp(A, Y, m)
        hs += all([round(v) for v in XS[l]] == X[l] for l in range(L))
    print("%3d   %11d/%d   %7d/%d   %10d/%d   %6d"
          % (m, ho, T, hs, T, hb, T, m * L))
print("full census of the matrix: %d single-item quotes" % (n * L))

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 6: The Hidden-Discount Matrix: Joint Sparsity across Public Conditions, and Basket Size. 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