Exploiting Kronecker Structures

Abstract

We study the important mathematical problem of approximating the inverse of low Kronecker-rank matrices in this same form. A traditional alternating least squares (ALS) scheme for solving such problems is presented, and we discuss two efficient solutions to the subproblems arising in the corresponding iterations. The first relies on a least-squares formulation while the second on a gradient-based solution from the literature. The former new approach is slightly less efficient but more robust as it does not involve forming the normal equations. We also advocate for employing a Nesterov-type acceleration in the higher level c{ALS} scheme. Usage of the resulting algorithm is evaluated in the context of approximating inverses in low Kronecker-rank form in order to preserve this structure for its continued exploitation in applications such as the matrix sign iterations and preconditioning linear systems.

Our theoretical study is motivated by two real-life practical applications in the field of adaptive optics (AO). We address each of these in terms of exploiting the Kronecker products featured within their problem formulations.

A minimum variance control scheme of wavefront control for atmospheric turbulence correction leads to a large-scale Kronecker structured constrained least-squares problem whose efficient solution is crucial for real-time implementation. Potential approaches based on the alternating direction method of multipliers (ADMM), projected alternating Barzilai-Borwein (PABB), and active sets (AS) methods are analyzed and compared in the context of exploiting the Kronecker structure of the system matrices using data from a partially realistic numerical study. The PABB approach is shown to be the most competitive, also with respective to alternative solutions exploiting only the sparsity of the system matrices instead of their Kronecker form as well.

The optimal design of a novel wavefront sensor called a sparse aperture mask (SAM) is also addressed in our work. Here Kronecker products appear when propagating wavefronts using the matrix-form of evaluating two dimensional Fourier transforms. The design problem is formulated in terms of a trade-off between the achievable light throughput of the mask and its ability to distinguish so-called Zernike modes that form a basis for the reconstructed wavefront. Two nonlinear optimization approaches for the solution are presented and discussed in terms of exploiting the Kronecker products by evaluating matrix-vector multiplications with them using a large but sparse philosophy. A final framework is proposed to combine the strengths of these in order to tackle the design problem.