Minimum Information Repair and Feasible Records

Conceptual map

1. I-04.01Missing dimension
2. I-04.02Lower bounds and constructions
3. I-04.03Admissible records
4. I-04.04Additive representations
5. I-04.05Constrained record dictionaries

1. Unrestricted dimension and feasible records

A rank bound counts how many unrestricted linear coordinates can repair a report. An actual reporting system offers a constrained dictionary whose records may have to be selected in larger bundles.

Let \(A:\mathbb{R}^{n}\to \mathbb{R}^{k}\) be the baseline report, \(B:\mathbb{R}^{n}\to \mathbb{R}^{r}\) the target, and \(r_{j}^{\top}\) the rows in a finite record dictionary \(\mathcal{D}\). For a subset \(S\subseteq \mathcal{D}\), let \(R_{S}\) stack its selected rows.

2. Exact subset criterion

The unrestricted lower bound remains \(d=\operatorname{rank}(B|\operatorname{\operatorname{ker}}(A))\). Every feasible repair has at least \(d\) records when each record is scalar. Equality depends on the geometry of the available rows.

3. A one-dimensional deficit requiring two records

Take latent state \(x\in \mathbb{R}^{3}\), baseline and target

Because \(B\) is scalar and varies on \(\operatorname{ker}(A)\), the unrestricted missing dimension is one. The dictionary contains only \(r_{1}^{\top}\)=[1,0,0] and \(r_{2}^{\top}\)=[0,1,0].

Selecting \(r_{1}\) leaves hidden direction (0,1,\(-1\)), which changes the target. Selecting \(r_{2}\) leaves (1,0,\(-1\)). Thus neither singleton repairs the target. Selecting both records gives

The feasible minimum is two, strictly above the unrestricted lower bound one.

4. Costs, minimal repairs, and algorithms

With positive record costs \(c_{j}\), the exact design problem minimizes \(\sum _{j\in S}c_{j}\) subject to (1). Inclusion-minimal repairs form an antichain, while cost-minimal repairs depend on the cost vector. Exhaustive search is exact for a small dictionary; mixed-integer or branch-and-bound methods can encode the rank or decoder constraints for larger systems.

Greedy selection needs a separate approximation theorem for its chosen objective. Exact rank gain can exhibit complementarities: a record with no standalone repair may be indispensable in a jointly sufficient bundle.

5. Implementation, exercises, and sources

Precompute a stable row basis for \(A\). For each candidate subset, append its rows, test whether every target row is reconstructed within tolerance, and retain the reconstruction residual and condition number. Exact rational arithmetic is preferable for small integer examples.

Exercises

1. Verify the unrestricted deficit and all four dictionary subsets in the example.
2. Add direct record \(r_{3}=x_{3}\) with cost three while the first two records cost one each; solve the cost problem.
3. Construct a dictionary with two distinct inclusion-minimal repairs of different cardinalities.

1. Alexander Schrijver, Theory of Linear and Integer Programming, chapters on polyhedra and combinatorial optimization.Finite record-selection formulations.
2. Gene H. Golub and Charles F. Van Loan, Matrix Computations, §5.5.Stable rank and row-space diagnostics.
3. III-15 · Set Functions, Möbius Inversion, and Modularity.Minimal enabling antichains and interaction structure.