This dissertation focuses on Kronecker compressed sensing, recovering multidimensional sparse signals from their linear projections on Kronecker product measurement matrices. Multidimensional signals are functions of different dimensions, each conveying a specific physical quantity and they arise in applications such as wireless communications and image processing. Kronecker product matrix naturally captures the multidimensional nature, making Kronecker compressed sensing a powerful framework for the recovery. Beyond the standard sparsity, practical signals typically have additional structures.We examine three structured sparsity models: hierarchical, Kronecker-supported, and Kronecker-structured. We start with algorithms and guarantees for the Kronecker-supported and Kronecker structured patterns, and then proceed to a unified algorithmic and theoretical framework, showing how leveraging structure in measurement matrices and sparsity patterns yields gains in accuracy and efficiency....

This work studies the problem of jointly estimating unknown parameters from Kronecker-structured multidimensional signals, which arises in applications like intelligent reflecting surface (IRS)-aided channel estimation. Exploiting the Kronecker structure, we decompose the estimation problem into smaller, independent subproblems across each dimension. Each subproblem is posed as a sparse recovery problem using basis expansion and solved using a novel off-grid sparse Bayesian learning (SBL)-based algorithm. Additionally, we derive probabilistic error bounds for the decomposition, quantify its denoising effect, and provide convergence analysis for off-grid SBL. Our simulations show that applying the algorithm to IRS-aided channel estimation improves accuracy and runtime compared to state-of-the-art methods through the low-complexity and denoising benefits of the decomposition step and the high-resolution estimation capabilities of off-grid SBL.

Kronecker compressed sensing refers to using Kronecker product matrices as sparsifying bases and measurement matrices in compressed sensing. This work focuses on the Kronecker compressed sensing problem, encompassing three sparsity structures: (i) a standard sparsity model with arbitrarily positioned nonzero entries, (ii) a hierarchical sparsity model where nonzero entries are concentrated in a few blocks, each with only a subset of nonzero entries, and (iii) a Kronecker-supported sparsity model where the support vector is a Kronecker product of smaller vectors. We present a hierarchal view of Kronecker compressed sensing that explicitly reveals a multiple-level sparsity pattern. This framework allows us to utilize the Kronecker structure of dictionaries and design a two-stage sparse recovery algorithm for different sparsity models. Further, we analyze the restricted isometry property of Kronecker-structured matrices under different sparsity models. Simulations show that our algorithm offers comparable recovery performance to state-of-the-art methods while significantly reducing runtime.

We study the recovery of a sparse vector with a Kronecker structure from an underdetermined linear system with a Kronecker-structured dictionary. This problem arises in several applications, such as the channel estimation of an intelligent reflecting surface-aided wireless system. Existing work only exploits the Kronecker structure in support of the sparse vector and solves the entire linear system jointly with high complexity. Instead, we decompose the original sparse recovery problem into multiple independent subproblems and solve them individually. We obtain the sparse vector as the Kronecker product of individual solutions, retaining its Kronecker structure. Besides, the subproblems exhibit reduced effective measurement noise. Our simulations demonstrate that our method has superior estimation accuracy and runtime compared to the existing work. We attribute the low complexity to the reduced dimensionality of the subproblems and improved accuracy to the denoising effect of the decomposition step.

This paper presents novel cascaded channel estimation techniques for an intelligent reflecting surface-aided multiple-input multiple-output system. Motivated by the channel angular sparsity at higher frequency bands, the channel estimation problem is formulated as a sparse vector recovery problem with an inherent Kronecker structure. We solve the problem using the sparse Bayesian learning framework which leads to a non-convex optimization problem. We offer two solution techniques to the problem based on alternating minimization and singular value decomposition. Our simulation results illustrate the superior performance of our methods in terms of accuracy and run time compared with the existing works.

In this work, we focus on partitioning dynamic graphs with two types of nodes (bi-colored), though not necessarily bipartite graphs. They commonly appear in communication network applications, e.g., one color being base stations, the other users, and the dynamic process being the varying connection status between base stations and moving users. We introduce a partition cost function that incorporates the coloring of the graph and propose solutions based on the generalized eigenvalue problem (GEVP) for the static two-way partition problem. The static multi-way partition problem is then handled by a heuristic based on the two-way partition problem. Regarding the adaptive partition, an eigenvector update-based method is proposed. Numerical experiments demonstrate the performance of the devised approaches.