An official website of the United States government
Multi-modal data are prevalent in many scientific fields. In this study, we consider the parameter estimation and variable selection for a multi-response regression using block-missing multi-modal data. Our method allows the dimensions of both the responses and the predictors to be large, and the responses to be incomplete and correlated, a common practical problem in high-dimensional settings. Our proposed method uses two steps to make a prediction from a multi-response linear regression model with block-missing multi-modal predictors. In the first step, without imputing missing data, we use all available data to estimate the covariance matrix of the predictors and the cross-covariance matrix between the predictors and the responses. In the second step, we use these matrices and a penalized method to simultaneously estimate the precision matrix of the response vector, given the predictors, and the sparse regression parameter matrix. Lastly, we demonstrate the effectiveness of the proposed method using theoretical studies, simulated examples, and an analysis of a multi-modal imaging data set from the Alzheimer’s Disease Neuroimaging Initiative.
more »
« less
Eigenvector Based Block Vector Synchronization with Applications to Ptychographic Imaging
We consider the problem of recovering a complex vector (up to a global unimodular constant) given noisy and incomplete outer product measurements. Such problems arise when implementing distributed clock synchronization schemes, radar autofocus methods, and phaseless signal recovery. This problem is known as vector synchronization and is a variant of the more common angular synchronization problem. In applications with windowed measurements and/or convolutional models - for example, phase retrieval from STFT magnitude data, the outer product measurement matrix is highly incomplete and has a block diagonal structure. We describe a vector synchronization technique which applies an eigenvector computation to blocks of this matrix followed by a block compatibility operation to piece together the final solution. We provide theoretical guarantees (in the noiseless case) and empirical simulations demonstrating the accuracy and efficiency of the method.
more »
« less
- Award ID(s):
- 2012238
- PAR ID:
- 10538474
- Publisher / Repository:
- IEEE
- Date Published:
- ISBN:
- 979-8-3503-0864-8
- Page Range / eLocation ID:
- 01 to 05
- Subject(s) / Keyword(s):
- Vector Synchronization Phaseless Imaging Magnitude-only STFT Inversion
- Format(s):
- Medium: X
- Location:
- Boulder, CO, USA
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract In synchronization problems, the goal is to estimate elements of a group from noisy measurements of their ratios. A popular estimation method for synchronization is the spectral method. It extracts the group elements from eigenvectors of a block matrix formed from the measurements. The eigenvectors must be projected, or ‘rounded’, onto the group. The rounding procedures are constructed ad hoc and increasingly so when applied to synchronization problems over non-compact groups. In this paper, we develop a spectral approach to synchronization over the non-compact group $$\mathrm{SE}(3)$$, the group of rigid motions of $$\mathbb{R}^{3}$$. We based our method on embedding $$\mathrm{SE}(3)$$ into the algebra of dual quaternions, which has deep algebraic connections with the group $$\mathrm{SE}(3)$$. These connections suggest a natural rounding procedure considerably more straightforward than the current state of the art for spectral $$\mathrm{SE}(3)$$ synchronization, which uses a matrix embedding of $$\mathrm{SE}(3)$$. We show by numerical experiments that our approach yields comparable results with the current state of the art in $$\mathrm{SE}(3)$$ synchronization via the spectral method. Thus, our approach reaps the benefits of the dual quaternion embedding of $$\mathrm{SE}(3)$$ while yielding estimators of similar quality.more » « less
-
We study algorithms for approximating the spectral density (i.e., the eigenvalue distribution) of a symmetric matrix A ∈ ℝn×n that is accessed through matrix-vector product queries. Recent work has analyzed popular Krylov subspace methods for this problem, showing that they output an ∈ · || A||2 error approximation to the spectral density in the Wasserstein-1 metric using O (1/∈ ) matrix-vector products. By combining a previously studied Chebyshev polynomial moment matching method with a deflation step that approximately projects off the largest magnitude eigendirections of A before estimating the spectral density, we give an improved error bound of ∈ · σℓ (A) using O (ℓ log n + 1/∈ ) matrix-vector products, where σℓ (A) is the ℓth largest singular value of A. In the common case when A exhibits fast singular value decay and so σℓ (A) « ||A||2, our bound can be much stronger than prior work. We also show that it is nearly tight: any algorithm giving error ∈ · σℓ (A) must use Ω(ℓ + 1/∈ ) matrix-vector products. We further show that the popular Stochastic Lanczos Quadrature (SLQ) method essentially matches the above bound for any choice of parameter ℓ, even though SLQ itself is parameter-free and performs no explicit deflation. Our bound helps to explain the strong practical performance and observed ‘spectrum adaptive’ nature of SLQ, and motivates a simple variant of the method that achieves an even tighter error bound. Technically, our results require a careful analysis of how eigenvalues and eigenvectors are approximated by (block) Krylov subspace methods, which may be of independent interest. Our error bound for SLQ leverages an analysis of the method that views it as an implicit polynomial moment matching method, along with recent results on low-rank approximation with single-vector Krylov methods. We use these results to show that the method can perform ‘implicit deflation’ as part of moment matching.more » « less
-
Krylov subspace methods are a ubiquitous tool for computing near-optimal rank kk approximations of large matrices. While "large block" Krylov methods with block size at least kk give the best known theoretical guarantees, block size one (a single vector) or a small constant is often preferred in practice. Despite their popularity, we lack theoretical bounds on the performance of such "small block" Krylov methods for low-rank approximation. We address this gap between theory and practice by proving that small block Krylov methods essentially match all known low-rank approximation guarantees for large block methods. Via a black-box reduction we show, for example, that the standard single vector Krylov method run for t iterations obtains the same spectral norm and Frobenius norm error bounds as a Krylov method with block size ℓ≥kℓ≥k run for O(t/ℓ)O(t/ℓ) iterations, up to a logarithmic dependence on the smallest gap between sequential singular values. That is, for a given number of matrix-vector products, single vector methods are essentially as effective as any choice of large block size. By combining our result with tail-bounds on eigenvalue gaps in random matrices, we prove that the dependence on the smallest singular value gap can be eliminated if the input matrix is perturbed by a small random matrix. Further, we show that single vector methods match the more complex algorithm of [Bakshi et al. `22], which combines the results of multiple block sizes to achieve an improved algorithm for Schatten pp-norm low-rank approximation.more » « less
-
We consider the problem of matrix approximation and denoising induced by the Kronecker product decomposition. Specifically, we propose to approximate a given matrix by the sum of a few Kronecker products of matrices, which we refer to as the Kronecker product approximation (KoPA). Because the Kronecker product is an extensions of the outer product from vectors to matrices, KoPA extends the low rank matrix approximation, and includes it as a special case. Comparing with the latter, KoPA also offers a greater flexibility, since it allows the user to choose the configuration, which are the dimensions of the two smaller matrices forming the Kronecker product. On the other hand, the configuration to be used is usually unknown, and needs to be determined from the data in order to achieve the optimal balance between accuracy and parsimony. We propose to use extended information criteria to select the configuration. Under the paradigm of high dimensional analysis, we show that the proposed procedure is able to select the true configuration with probability tending to one, under suitable conditions on the signal-to-noise ratio. We demonstrate the superiority of KoPA over the low rank approximations through numerical studies, and several benchmark image examples.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/CISA60639.2024.10576263
