Fast Algorithms for Monotone Lower Subsets of Kronecker Least Squares Problems

Osman Asif Malik, Yiming Xu, Nuojin Cheng, Stephen Becker, Alireza Doostan, Akil Narayan

Abstract

Approximate solutions to large least squares problems can be computed efficiently using leverage score-based row-sketches, but directly computing the leverage scores, or sampling according to them with naive methods, still requires an expensive manipulation and processing of the design matrix. In this paper we develop efficient leverage score-based sampling methods for matrices with certain Kronecker product-type structure; in particular we consider matrices that are monotone lower column subsets of Kronecker product matrices. Our discussion is general, encompassing least squares problems on infinite domains, in which case matrices formally have infinitely many rows. We briefly survey leverage score-based sampling guarantees from the numerical linear algebra and approximation theory communities, and follow this with efficient algorithms for sampling when the design matrix has Kronecker-type structure. Our numerical examples confirm that sketches based on exact leverage score sampling for our class of structured matrices achieve superior residual compared to approximate leverage score sampling methods.

Introduction

In the field of randomized numerical linear algebra, solving large-scale least squares problems ($Ax \approx b$) often involves "sketching." This technique involves sampling a small subset of rows from the massive matrix $A$ to solve a significantly smaller, more manageable problem. The gold standard for row selection is sampling according to leverage scores, which quantify the influence of each row on the overall fit.

However, a fundamental challenge exists: computing exact leverage scores typically requires a QR decomposition of the entire matrix $A$. For high-dimensional problems, this computation can be more expensive than solving the original least squares problem directly. Consequently, researchers often resort to uniform sampling or cheap approximations, which frequently result in higher estimation errors. This paper addresses this bottleneck for a specific, widely used class of structured matrices: those formed by a subset of columns from a large Kronecker product matrix.

The Monotone Lower Subset Property

The efficiency of the proposed method hinges on the "lower subset" (or downward-closed) property of the column index set. In the context of multivariate polynomial approximations, such as Polynomial Chaos Expansions, this property implies that if a high-degree interaction between variables is included in the model, all simpler constituent interactions must also be included.

Permutation and Structural Flexibility

While the algorithm requires a lower subset structure, the authors demonstrate that this requirement is more flexible than it appears. Many index sets that do not initially satisfy the property can be transformed into lower subsets through appropriate reordering or permutation of the indices.

Permutations of index sets to achieve the monotone lower subset property.

As shown in Figure 1, various index sets $\mathcal{J}$ can be permuted into forms like $\tilde{\pi}(\tilde{\mathcal{J}})$ that satisfy the downward-closed requirement. This flexibility significantly broadens the range of problems to which the proposed sampling algorithm can be applied.

Efficient Exact Leverage Score Sampling

The core contribution is a two-step multivariate sampling procedure (Algorithm 1) that achieves exact leverage score sampling without ever forming the full matrix $A$.

  1. Index Selection: A column index is sampled uniformly from the lower subset.
  2. Dimension-wise Sampling: Row indices are sampled independently for each dimension using the much smaller factor matrices of the Kronecker product.

Theorem 3.2 in the paper provides the rigorous proof that this decoupled process is mathematically equivalent to sampling from the exact leverage score distribution of the full subset matrix. This reduces computational complexity from a product of dimensions to a sum of dimensions, turning a prohibitively expensive task into a routine preprocessing step.

Experimental Results

The algorithm was evaluated using three benchmark models common in uncertainty quantification (UQ):

  • Nonlinear Duffing Oscillator ($D=3$): A physics model of a vibrating system.
  • Ishigami Function ($D=3$): A highly non-linear mathematical benchmark.
  • Lithium-ion Battery RUL ($D=7$): A practical application predicting the "Remaining Useful Life" of batteries.

In all experiments, the proposed Exact Leverage Sampling consistently outperformed both uniform sampling and approximate Tensor Product (TP) leverage sampling. Notably, in the 7D battery life example, approximate TP sampling performed no better than random uniform sampling, while the exact method maintained high stability and accuracy.

Conclusion

This work demonstrates that for matrices with Kronecker-type structure and lower subset column indices, exact leverage score sampling is not only possible but computationally efficient. By exploiting structural properties, the authors provide a "Gold Standard" sampling method that avoids the accuracy trade-offs typical of approximate sketching techniques. Future work may involve automating the identification of optimal permutations and extending the logic to more general "approximate" lower subsets.

Summary updated

Abstract

Approximate solutions to large least squares problems can be computed efficiently using leverage score-based row-sketches, but directly computing the leverage scores, or sampling according to them with naive methods, still requires an expensive manipulation and processing of the design matrix. In this paper we develop efficient leverage score-based sampling methods for matrices with certain Kronecker product-type structure; in particular we consider matrices that are monotone lower column subsets of Kronecker product matrices. Our discussion is general, encompassing least squares problems on infinite domains, in which case matrices formally have infinitely many rows. We briefly survey leverage score-based sampling guarantees from the numerical linear algebra and approximation theory communities, and follow this with efficient algorithms for sampling when the design matrix has Kronecker-type structure. Our numerical examples confirm that sketches based on exact leverage score sampling for our class of structured matrices achieve superior residual compared to approximate leverage score sampling methods.
BibTeX
@misc{malik2022fast,
  author = {Osman Asif Malik and Yiming Xu and Nuojin Cheng and Stephen Becker and Alireza Doostan and Akil Narayan},
  title = {{Fast Algorithms for Monotone Lower Subsets of Kronecker Least Squares Problems}},
  year = {2022},
  eprint = {2209.05662},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.05662},
}
Figure