关于「暗折矩阵:多个公开条件的联合稀疏与篮子大小」,《稀疏探针与暗折重构》给出的定量结论是什么?

结论:多个公开条件下的暗折并排成一张矩阵,带暗折的商品在各条件之间大体相同,这叫联合稀疏。程序 p61 显示,联合信息让贪心算法 SOMP 明显胜过逐列 OMP,但在非负的 0 与 1 篮子上,逐列一范数仍然最好:24 次报价起整张矩阵全对,4 个条件合计 96 次,而全盘抽样要 320 次。程序 p62 显示篮子大小有两头的代价:每篮 2 件时要 78 次报价,比全盘抽样还多;每篮 15 件以上时 16 次即可,但经手件数随篮子变大而上升。到这里,数学部分已经完整。下一章回到两部原典:《孙子》说先知「必取于人」,香农说信号由它的样本完全决定;它们说对了什么,又在哪里被今天的数据改写。

数据口径:只要暗折是稀疏的,把商品随机组合成购物车、只读结算总额,所需报价次数大致与暗折数乘以商品数对暗折数之比的对数成正比,远少于商品数;在非负约束下极小化一范数,无噪声时得到的是精确的表。 书中商品、金额、成本与竞品均为示意;全部计算由书中程序生成;本书是非个人化经营参考,不是法律意见。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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
查看完整验算程序
# 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))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《压缩感知一范数极小化、神秘访客稀疏探针与竞品暗折矩阵精确重构母典》第 6 章「暗折矩阵:多个公开条件的联合稀疏与篮子大小」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 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}
}

本书其他章节结论