The manuscript parameter recipe for a sparse measurement layout
Fix an integer beta>=1, n>=20, lambda=ceil(log2 n), and nu=ceil(log2 lambda). Assume b,w<=lambda^beta and n<=M<=bn. The recipe is r=floor(sqrt(lambda)/nu^2), Q=floor(lambda/(128*nu)), R=(beta+3)*ceil(sqrt(lambda)), tau=1/(r*lambda), epsilon=1/(b*r^2*lambda), and D=r^(2Q). Here r counts groups, Q counts evaluation points, R bounds replacement degree, and epsilon bounds the exceptional basis fraction. This is a candidate recipe, not an automatic valid layout: if r<2 or Q<=R, stop before using its reciprocal parameters. Later checks require R>=32, 6R<=Q, balanced-schedule inequalities, and the tail bound.
0
1
Tags
Math
Related
Counting the auxiliary substitution and restriction pairs
Why operation counts need bounds on integer bit lengths
Bounding coefficients produced by the parity-lift construction
The quantitative contract for the initial sparse checks
The stated fast-contraction theorem and its input requirements
Grouping tests and variables before indexing incidence subsets
Choosing enough residue-field elements for interpolation
Learn After
Related
Counting the auxiliary substitution and restriction pairs
Why operation counts need bounds on integer bit lengths
Bounding coefficients produced by the parity-lift construction
The quantitative contract for the initial sparse checks
The stated fast-contraction theorem and its input requirements
Grouping tests and variables before indexing incidence subsets
Choosing enough residue-field elements for interpolation