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.
Perhaps the most direct approach for analyzing the RICs of the KR product matrix is to use the eigenvalue interlacing theorem @cite_1 , which relates the singular values of any @math -column submatrix of the KR product between two matrices to the singular values of their Kronecker product. This is possible because any @math columns of the KR product can together be interpreted as a submatrix of the Kronecker product. However, barring the maximum and minimum singular values of the Kronecker product, there is no available explicit characterization of its non-extremal singular values that can be used to obtain tight bounds for the @math -RIC of the KR product. Bounding the RIC using the extreme singular values of the Kronecker product matrix turns out to be too loose to be useful. In this context, it is noteworthy to mention that an upper bound for the @math -RIC of the Kronecker product is derived in terms of the @math -RICs of the input matrices in @cite_6 @cite_28 . However, the @math -RIC of the Khatri-Rao product is yet to be analyzed.
@cite_28 @cite_1 @cite_6
210359992 2001380973
1. Basic Concepts. 2. Nonparametric Methods. 3. Parametric Methods for Rational Spectra. 4. Parametric Methods for Line Spectra. 5. Filter Bank Methods. 6. Spatial Methods. Appendix A: Linear Algebra and Matrix Analysis Tools. Appendix B: Cramer-Rao Bound Tools. Appendix C: Model Order Selection Tools. Appendix D: Answers to Selected Exercises. Bibliography. References Grouped by Subject. Subject Index. Compressive sensing (CS) is an emerging approach for the acquisition of signals having a sparse or compressible representation in some basis. While the CS literature has mostly focused on problems involving 1-D signals and 2-D images, many important applications involve multidimensional signals; the construction of sparsifying bases and measurement systems for such signals is complicated by their higher dimensionality. In this paper, we propose the use of Kronecker product matrices in CS for two purposes. First, such matrices can act as sparsifying bases that jointly model the structure present in all of the signal dimensions. Second, such matrices can represent the measurement protocols used in distributed settings. Our formulation enables the derivation of analytical bounds for the sparse approximation of multidimensional signals and CS recovery performance, as well as a means of evaluating novel distributed measurement schemes.