关于「不必全盘抽样:篮子报价、稀疏暗折与一范数的精确重构」,《稀疏探针与暗折重构》给出的定量结论是什么?
结论:第一章核对并修正立项命题的出处,用分数精确的单纯形法以 12 次篮子报价还原 40 件商品里的 3 笔暗折,而最小二乘把它们摊满全表,最坏一格偏离 26.73 元;并量出排程常数,报价占商品数的比例可降到 0.0825。
数据口径:只要暗折是稀疏的,把商品随机组合成购物车、只读结算总额,所需报价次数大致与暗折数乘以商品数对暗折数之比的对数成正比,远少于商品数;在非负约束下极小化一范数,无噪声时得到的是精确的表。 书中商品、金额、成本与竞品均为示意;全部计算由书中程序生成;本书是非个人化经营参考,不是法律意见。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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 |
核心公式
\[y = \sum_{j \in \text{basket}} p_j - T = \sum_{j \in \text{basket}} x_j .\]
查看完整验算程序
# 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))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《压缩感知一范数极小化、神秘访客稀疏探针与竞品暗折矩阵精确重构母典》第 1 章「不必全盘抽样:篮子报价、稀疏暗折与一范数的精确重构」(版本 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}
}