Bottom-up low-rank recompression of block contributions

Let $b=(\tau ,\sigma )$ be an admissible leaf of the finite block-cluster partition in H-matrix block representation. A factor-sum tree for $b$ is a finite rooted binary tree whose leaves carry factor pairs $U_v\in {\mathbb{F}}^{\tau \times r_v}$, $V_v\in {\mathbb{F}}^{\sigma \times r_v}$ for exact contributions $M_v=U_v{V}_v^{\ast }$; each internal node denotes the sum of the exact matrices denoted by its two children. Here $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$, $\ast$ is conjugate transpose, and all factors have the displayed finite dimensions.

Input: Such a tree, a rank cap $k\ge 1$, node tolerances ${\theta }_v\ge 0$ whose sum over all nodes is at most a requested block tolerance ${\delta }_b\ge 0$, and the procedures/results Core-SVD recompression with rank and error tolerances and Core-SVD recompression is best at the declared Frobenius tolerance.

Procedure: Traverse the tree in postorder. At a leaf, pass its exact factor pair to core-SVD recompression. At an internal node, concatenate the returned child factor pairs, which represents the sum of the two child approximations, and pass that pair to core-SVD recompression. At every node use effective core cap $k_b=\min (k,\mathrm{\mid }\tau \mathrm{\mid },\mathrm{\mid }\sigma \mathrm{\mid })$ and tolerance ${\theta }_v$. If any call returns tolerance-not-met, return that status and node. On success, retain its factors and exact discarded-tail norm ${\rho }_v$. Define the node's reported error bound by $e_v={\rho }_v$ at a leaf and $e_v=e_{v_1}+e_{v_2}+{\rho }_v$ at an internal node. If all calls succeed, return the root factors and $e_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}$. Then the root matrix has rank at most $k$ and its Frobenius error from the sum of all leaf contributions is at most $e_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}\le {\sum }_v{\theta }_v\le {\delta }_b$. A failed call means only that this chosen tree and its assigned local budgets did not produce a certificate; it does not assert that no rank-$k$ approximation of the full sum meets ${\delta }_b$.

Near blocks are not passed to this routine: they are assembled and stored densely and exactly. For a leaf carrying a dense contribution $D\in {\mathbb{F}}^{m\times n}$, use the exact factor pair $(D,I_n)$, where $I_n$ is the identity matrix; the routine may then compress it under its assigned tolerance.

The rank and error guarantees are proved in Bottom-up factor-sum recompression has the reported rank and Frobenius error bound ↗.