Cube sampling preserves prescribed inclusion probabilities, yet minimizing the variance of individual rounding steps need not minimize the error of the final matrix sketch. We study this gap through the complete flight-and-landing process and develop an efficient implementation of a Gram-aware sampling rule. For a specified class of legal actions and landing procedures, we show how residual balance infeasibility forces terminal mutual exclusion, yielding policy-invariant covariance structure and conditions for exact optimality and quantitative near-optimality. Conversely, an explicit six-unit construction exhibits a unique locally optimal update with strictly positive complete-path regret, revealing the role of subsequent branching and landing. For rank-one positive semidefinite contributions, the resulting risk analysis connects Gram approximation to PCA reconstruction and subspace error. We then introduce Incremental Gram-Cube (IGC), which combines cross-step Gram reuse, an endpoint nullspace basis, and direct two-dimensional direction evaluation to accelerate a directional-energy surrogate on four-unit buffers. Under matched tie conventions, the implementation preserves the sampling rule in exact arithmetic. On 24 development cases spanning synthetic populations, real-data subsets, and larger synthetic inputs, IGC reduces end-to-end sampling-and-estimation time by 7.30–12.20% across the three groups relative to an already cached implementation of the same rule. All 9,216 paired evaluation draws produce identical selected indices and Frobenius errors. These results characterize when local Cube decisions suffice and demonstrate how matrix-aware updates can be computed with less overhead.
Response to Reviewer NWxo: A clearer explanation of the problem and contributions
Thank you for taking the time to read our paper. We are sorry that the original presentation did not make the problem and contributions clear. It introduced too many terms and theorems before explaining the sampling problem. Your feedback prompted a substantial revision.
We have rewritten the abstract and introduction, defined terms before the results, clarified notation, and moved detailed implementation derivations to Appendix C. Figure 1 connects sampled rows, matrix error, and principal component analysis (PCA) bounds. The main idea is as follows.
1. The starting point: keeping a small set of actual rows.
Suppose a data matrix contains many observations, and we want to retain a smaller set of real rows. By weighting the selected rows appropriately, we can estimate the full matrix's Gram matrix, which summarizes second moments and cross-products between features. This supports PCA and covariance analysis. Our task-specific extensions also examine classification, correlation estimation, clustering, and tail-frequency estimation. The experiments include activity recognition, handwritten-digit data, and financial time series.
Cube is an existing balanced-sampling method. It starts with each row's desired selection probability and randomly adjusts several probabilities together while preserving chosen totals. Zero means discard the row; one means keep it. This is flight. When balanced moves can no longer continue, randomized landing rounds the remaining probabilities. Each row keeps its prescribed selection chance, although landing may relax auxiliary balance. We study how to choose the moves within this process.
2. The question: which rows should be selected together?
Consider four rows: two copies of (1,0) and two copies of (0,1), with two rows to be selected. Selecting one of each type preserves both directions and, after reweighting, the Gram matrix exactly. Selecting a duplicate pair loses one direction in each sample. Both designs can give every row the same selection probability of one half. The difference is which rows appear together.
Cube makes these joint-selection decisions through a sequence of random moves. A rule that chooses the move with the smallest immediate variance may leave a poor choice later. We therefore study the expected squared error of the final matrix estimate, including the last rounding step. This is what we mean by complete-path risk.
3. What the theory and algorithms contribute.
First, we identify when balance constraints themselves limit how much these choices can matter. Some rows cannot be selected during flight because doing so would make the remaining balance impossible. Under the stated pairwise landing rule, at most one of these rows can enter the final sample. This fixes part of the joint-selection structure for every admissible policy. If that part accounts for all the error, every policy has the same risk; if the remaining contribution is small, we obtain a quantitative near-optimality bound.
Second, an exact six-row example shows the complementary case: the uniquely best immediate move leads to a worse final estimate because of subsequent branches and landing. These two results explain when local decisions are sufficient and when looking ahead matters. For row outer products, the analysis becomes a Gram-error analysis and supplies PCA error bounds (Secs. 3-6).
The computational contributions follow two distinct routes. Incremental Gram-Cube (IGC) computes the same specified direction rule with fewer local calculations. Task-specific coupling instead changes which rows enter together, using contributions relevant to the task. Sections 7-9 now distinguish these routes explicitly.
4. The measured outcomes and supporting evidence.
IGC reduces complete-draw time by 7.30-12.20% relative to the cached implementation of the same rule, with 9,216 identical paired outputs.
The separate task-specific designs show downstream gains under matched information and row budgets. With identical groups and 128 selected rows, classification accuracy improves by 0.382 and 1.179 percentage points on HAR and ISOLET, at 5.6% and 6.5% additional complete cost (Table 3). This demonstrates a concrete use of controlling joint selection, with its computational cost measured alongside quality.
The results above come from executed experiments and exact computations. The anonymous supplement provides code, saved inputs, seeds, per-draw measurements, and commands to regenerate the tables. It retains all 46,560 observations from the new task studies, including unfavorable outcomes. Exact constructions have independent rational-arithmetic checks. Historical archive coverage is stated in the README.
We would be grateful if you could revisit the revised introduction, Figure 1, and Sections 3-6, which now explain the sampling problem and central mechanism before the formal results.