关于「一范数写成线性规划:两阶段单纯形、对偶证书与探针设计体检」,《稀疏探针与暗折重构》给出的定量结论是什么?
结论:第二章把一范数写成两阶段单纯形,讲退化与扰动,开出唯一性证书,并给出篮子设计体检:零列与同列把三格支撑的还原比例从 0.969 拉到 0.704。
数据口径:只要暗折是稀疏的,把商品随机组合成购物车、只读结算总额,所需报价次数大致与暗折数乘以商品数对暗折数之比的对数成正比,远少于商品数;在非负约束下极小化一范数,无噪声时得到的是精确的表。 书中商品、金额、成本与竞品均为示意;全部计算由书中程序生成;本书是非个人化经营参考,不是法律意见。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.704, 0.969
| clean design: zero columns [], identical pairs [] | |
| k | 1: 20 of 20 exact (1.000); failures on 5/12/17: 0 of 0 |
| k | 2: 190 of 190 exact (1.000); failures on 5/12/17: 0 of 0 |
| k | 3: 1105 of 1140 exact (0.969); failures on 5/12/17: 12 of 35 |
| flawed design: zero columns [17], identical pairs [(5, 12)] | |
| k | 1: 18 of 20 exact (0.900); failures on 5/12/17: 2 of 2 |
| k | 2: 153 of 190 exact (0.805); failures on 5/12/17: 37 of 37 |
| k | 3: 802 of 1140 exact (0.704); failures on 5/12/17: 327 of 338 |
查看完整验算程序
# Chapter 2. p22: audit a basket design before anyone goes shopping.
# Model: n = 20 items, m = 10 basket quotes, each item in a basket with
# chance 1/2 (seeded), then two planted flaws seen in real plans: item
# 12 always rides with item 5 (identical columns) and item 17 is never
# put in any basket (zero column). For nonnegative basis pursuit the
# outcome depends only on which cells are nonzero, so we test every
# support of size 1, 2 and 3 with x = 1 there (1,350 linear programs,
# float simplex) and count the supports recovered exactly.
import itertools
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 audit(A, n, k):
good, bad = 0, []
for S in itertools.combinations(range(n), k):
y = [len([j for j in S if A[i][j]]) for i in range(len(A))]
xh, _, _ = lp_min(A, y, [1] * n)
x = [1 if j in S else 0 for j in range(n)]
if xh is not None and max(abs(a - b)
for a, b in zip(xh, x)) < 1e-6:
good += 1
else:
bad.append(S)
return good, bad
n, m = 20, 10
rng = random.Random(20261122)
A = [[1 if rng.random() < 0.5 else 0 for _ in range(n)]
for _ in range(m)]
clean = [r[:] for r in A]
for r in A:
r[12] = r[5]
r[17] = 0
for name, D in (("clean design", clean), ("flawed design", A)):
cols = [tuple(D[i][j] for i in range(m)) for j in range(n)]
zero = [j for j in range(n) if not any(cols[j])]
twins = [(a, b) for a, b in itertools.combinations(range(n), 2)
if cols[a] == cols[b]]
print("%s: zero columns %s, identical pairs %s"
% (name, zero, twins))
for k in (1, 2, 3):
good, bad = audit(D, n, k)
tot = math.comb(n, k)
hit = len([S for S in bad if 17 in S or (5 in S) != (12 in S)
or (5 in S and 12 in S)])
print(" k = %d: %4d of %4d exact (%.3f); failures on"
" 5/12/17: %d of %d"
% (k, good, tot, good / tot, hit, len(bad)))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《压缩感知一范数极小化、神秘访客稀疏探针与竞品暗折矩阵精确重构母典》第 2 章「一范数写成线性规划:两阶段单纯形、对偶证书与探针设计体检」(版本 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}
}