The columnwise Khatri–Rao product of two matrices is an important matrix type, reprising its role as a structured sensing matrix in many fundamental linear inverse problems. Robust signal recovery in such inverse problems is often contingent on proving the restricted isometry property (RIP) of a certain system matrix expressible as a Khatri–Rao product of two matrices. In this paper, we analyze the RIP of a generic columnwise Khatri–Rao product matrix by deriving two upper bounds for its @math th order restricted isometry constant ( @math -RIC) for different values of @math . The first RIC bound is computed in terms of the individual RICs of the real-valued input matrices participating in the Khatri–Rao product. The second RIC bound is probabilistic and is specified in terms of the input matrix dimensions. We show that the Khatri–Rao product of a pair of @math sized random matrices comprising independent and identically distributed sub-Gaussian entries satisfies @math -RIP with arbitrarily high probability, provided @math exceeds @math . This is a substantially milder condition compared to @math rows needed to guarantee @math -RIP of the input sub-Gaussian random matrices participating in the Khatri–Rao product. Our RIC bounds confirm that the Khatri–Rao product exhibits stronger restricted isometry compared to its constituent matrices for the same RIP order. The proposed RIC bounds are potentially useful in obtaining improved performance guarantees in several sparse signal recovery and tensor decomposition problems.
In @cite_22 , the isometry property of the Kronecker product @math is analyzed in the @math -norm sense for the restricted class of input vectors expressible as vectorized @math -distributed sparse matrices, wherein, @math and @math are the adjacency matrices of two independent uniformly random @math -left regular bipartite graphs. In this paper, we instead analyze the restricted isometry of the columnwise Khatri-Rao product @math , which is equivalent to the RIP of the Kronecker product @math with respect to vectorized sparse diagonal matrices. In our work, we assume that input matrices @math and @math are random with independent subgaussian elements.
@cite_22
2003571173
This paper considers the problem of recovering an unknown sparse p×p matrix X from an m×m matrix Y=AXB T , where A and B are known m×p matrices with m≪p. The main result shows that there exist constructions of the sketching matrices A and B so that even if X has O(p) nonzeros, it can be recovered exactly and efficiently using a convex program as long as these nonzeros are not concentrated in any single row column of X. Furthermore, it suffices for the size of Y (the sketch dimension) to scale as m = O(√(# nonzeros in X) × log p). The results also show that the recovery is robust and stable in the sense that if X is equal to a sparse matrix plus a perturbation, then the convex program we propose produces an approximation with accuracy proportional to the size of the perturbation. Unlike traditional results on sparse recovery, where the sensing matrix produces independent measurements, our sensing operator is highly constrained (it assumes a tensor product structure). Therefore, proving recovery guarantees require nonstandard techniques. Indeed, our approach relies on a novel result concerning tensor products of bipartite graphs, which may be of independent interest. This problem is motivated by the following application, among others. Consider a p×n data matrix D, consisting of n observations of p variables. Assume that the correlation matrix X:=DD T is (approximately) sparse in the sense that each of the p variables is significantly correlated with only a few others. Our results show that these significant correlations can be detected even if we have access to only a sketch of the data S=AD with A ∈ R m×p .