An official website of the United States government
This paper introduces a novel framework called Mode-wise Principal Subspace Pursuit (MOP-UP) to extract hidden variations in both the row and column dimensions for matrix data. To enhance the understanding of the framework, we introduce a class of matrix-variate spiked covariance models that serve as inspiration for the development of the MOP-UP algorithm. The MOP-UP algorithm consists of two steps: Average Subspace Capture (ASC) and Alternating Projection. These steps are specifically designed to capture the row-wise and column-wise dimension-reduced subspaces which contain the most informative features of the data. ASC utilizes a novel average projection operator as initialization and achieves exact recovery in the noiseless setting. We analyse the convergence and non-asymptotic error bounds of MOP-UP, introducing a blockwise matrix eigenvalue perturbation bound that proves the desired bound, where classic perturbation bounds fail. The effectiveness and practical merits of the proposed framework are demonstrated through experiments on both simulated and real datasets. Lastly, we discuss generalizations of our approach to higher-order data.
more »
« less
"Hilbert Space Geometry of Quadratic Covariance Bounds, Asilomar Conference on Signals, Systems, and Computers, Oct 30-N0v 1, 2018.
In this paper, we study the geometry of quadratic covariance bounds on the estimation error covariance, in a properly defined Hilbert space of random variables. We show that a lower bound on the error covariance may be represented by the Grammian of the error score after projection onto the subspace spanned by the measurement scores. The Grammian is defined with respect to inner products in a Hilbert space of second order random variables. This geometric result holds for a large class of quadratic covariance bounds including the Barankin, Cramer-Rao, and Bhattacharyya bounds, where each bound is characterized by its corresponding measurement scores. When parameters consist of essential parameters and nuisance parameters, the Cram´er-Rao covariance bound is the inverse of the Grammian of essential scores after projection onto the subspace orthogonal to the subspace spanned by the nuisance scores. In two examples, we show that for complex multivariate normal measurements with parameterized mean or covariance, there exist well-known Euclidean space geometries for the general Hilbert space geometry derived in this paper.
more »
« less
- Award ID(s):
- 1712788
- PAR ID:
- 10058158
- Date Published:
- Journal Name:
- Conference record - Asilomar Conference on Signals, Systems, & Computers
- ISSN:
- 1058-6393
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Principal Component Analysis (PCA) and Kernel Principal Component Analysis (KPCA) are fundamental methods in machine learning for dimensionality reduction. The former is a technique for finding this approximation in finite dimensions and the latter is often in an infinite dimensional Reproducing Kernel Hilbert-space (RKHS). In this paper, we present a geometric framework for computing the principal linear subspaces in both situations as well as for the robust PCA case, that amounts to computing the intrinsic average on the space of all subspaces: the Grassmann manifold. Points on this manifold are defined as the subspaces spanned by K -tuples of observations. The intrinsic Grassmann average of these subspaces are shown to coincide with the principal components of the observations when they are drawn from a Gaussian distribution. We show similar results in the RKHS case and provide an efficient algorithm for computing the projection onto the this average subspace. The result is a method akin to KPCA which is substantially faster. Further, we present a novel online version of the KPCA using our geometric framework. Competitive performance of all our algorithms are demonstrated on a variety of real and synthetic data sets.more » « less
-
Oja's algorithm for Streaming Principal Component Analysis (PCA) for n data-points in a d dimensional space achieves the same sin-squared error O(r𝖾𝖿𝖿/n) as the offline algorithm in O(d) space and O(nd) time and a single pass through the datapoints. Here r𝖾𝖿𝖿 is the effective rank (ratio of the trace and the principal eigenvalue of the population covariance matrix Σ). Under this computational budget, we consider the problem of sparse PCA, where the principal eigenvector of Σ is s-sparse, and r𝖾𝖿𝖿 can be large. In this setting, to our knowledge, \textit{there are no known single-pass algorithms} that achieve the minimax error bound in O(d) space and O(nd) time without either requiring strong initialization conditions or assuming further structure (e.g., spiked) of the covariance matrix. We show that a simple single-pass procedure that thresholds the output of Oja's algorithm (the Oja vector) can achieve the minimax error bound under some regularity conditions in O(d) space and O(nd) time. We present a nontrivial and novel analysis of the entries of the unnormalized Oja vector, which involves the projection of a product of independent random matrices on a random initial vector. This is completely different from previous analyses of Oja's algorithm and matrix products, which have been done when the r𝖾𝖿𝖿 is bounded.more » « less
-
Fisher information is a lower bound on the uncertainty in the statistical estimation of classical and quantum mechanical parameters. While some deterministic dynamical systems are not subject to random fluctuations, they do still have a form of uncertainty. Infinitesimal perturbations to the initial conditions can grow exponentially in time, a signature of deterministic chaos. As a measure of this uncertainty, we introduce another classical information, specifically for the deterministic dynamics of isolated, closed, or open classical systems not subject to noise. This classical measure of information is defined with Lyapunov vectors in tangent space, making it less akin to the classical Fisher information and more akin to the quantum Fisher information defined with wavevectors in Hilbert space. Our analysis of the local state space structure and linear stability leads to upper and lower bounds on this information, giving it an interpretation as the net stretching action of the flow. Numerical calculations of this information for illustrative mechanical examples show that it depends directly on the phase space curvature and speed of the flow.more » « less
-
Cassio de Campos; Marloes H. Maathuis (Ed.)When data contains measurement errors, it is necessary to make modeling assumptions relating the error-prone measurements to the unobserved true values. Work on measurement error has largely focused on models that fully identify the parameter of interest. As a result, many practically useful models that result in bounds on the target parameter -- known as partial identification -- have been neglected. In this work, we present a method for partial identification in a class of measurement error models involving discrete variables. We focus on models that impose linear constraints on the tar- get parameter, allowing us to compute partial identification bounds using off-the-shelf LP solvers. We show how several common measurement error assumptions can be composed with an extended class of instrumental variable-type models to create such linear constraint sets. We further show how this approach can be used to bound causal parameters, such as the average treatment effect, when treatment or outcome variables are measured with error. Using data from the Oregon Health Insurance Experiment, we apply this method to estimate bounds on the effect Medicaid enrollment has on depression when depression is measured with error.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
