An official website of the United States government
This paper studies linear regression models for high dimensional multi-response data with a hybrid quantum computing algorithm. We propose an intuitively appealing estimation method based on identifying the linearly independent columns in the coefficient matrix. Our method relaxes the low rank constraint in the existing literature and allows the rank to diverge with dimensions. The linearly independent columns are selected by a novel non-oracular quantum search (NQS) algorithm which is significantly faster than classical search methods implemented on electronic computers. Besides, NQS achieves a near optimal computational complexity as existing quantum search algorithms but does not require any oracle information of the solution state. We prove the proposed estimation procedure enjoys desirable theoretical properties. Intensive numerical experiments are also conducted to demonstrate the finite sample performance of the proposed method, and a comparison is made with some popular competitors. The results show that our method outperforms all of the alternative methods under various circumstances.
more »
« less
Toroidal Coordinates: Decorrelating Circular Coordinates with Lattice Reduction
The circular coordinates algorithm of de Silva, Morozov, and Vejdemo-Johansson takes as input a dataset together with a cohomology class representing a 1-dimensional hole in the data; the output is a map from the data into the circle that captures this hole, and that is of minimum energy in a suitable sense. However, when applied to several cohomology classes, the output circle-valued maps can be "geometrically correlated" even if the chosen cohomology classes are linearly independent. It is shown in the original work that less correlated maps can be obtained with suitable integer linear combinations of the cohomology classes, with the linear combinations being chosen by inspection. In this paper, we identify a formal notion of geometric correlation between circle-valued maps which, in the Riemannian manifold case, corresponds to the Dirichlet form, a bilinear form derived from the Dirichlet energy. We describe a systematic procedure for constructing low energy torus-valued maps on data, starting from a set of linearly independent cohomology classes. We showcase our procedure with computational examples. Our main algorithm is based on the Lenstra-Lenstra-Lovász algorithm from computational number theory.
more »
« less
- PAR ID:
- 10445619
- Editor(s):
- Chambers, Erin W.; Gudmundsson, Joachim
- Publisher / Repository:
- Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- Date Published:
- Journal Name:
- Leibniz international proceedings in informatics
- Volume:
- 258
- Issue:
- 57
- ISSN:
- 1868-8969
- Page Range / eLocation ID:
- 57:1 - 57:20
- Subject(s) / Keyword(s):
- dimensionality reduction lattice reduction Dirichlet energy harmonic cocycle Mathematics of computing → Algebraic topology
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We provide a uniform bound for the index of cohomology classes over semiglobal fields (i.e., over one-variable function fields over a complete discretely valued field K). The bound is given in terms of the analogous data for the residue field of K and its finitely generated extensions of transcendence degree at most one. We also obtain analogous bounds for collections of cohomology classes. Our results provide recursive formulas for function fields over higher rank complete discretely valued fields, and explicit bounds in some cases when the information on the residue field is known. In the process, we prove a splitting result for cohomology classes of degree 3 in the context of surfaces over finite fields. ∗more » « less
-
Abstract We prove that 2-dimensionalQ-valued maps that are stationary with respect to outer and inner variations of the Dirichlet energy are Hölder continuous and that the dimension of their singular set is at most one. In the course of the proof we establish a strong concentration-compactness theorem for equicontinuous maps that are stationary with respect to outer variations only, and which holds in every dimensions.more » « less
-
Abstract A Bayesian method is proposed for variable selection in high-dimensional matrix autoregressive models which reflects and exploits the original matrix structure of data to (a) reduce dimensionality and (b) foster interpretability of multidimensional relationship structures. A compact form of the model is derived which facilitates the estimation procedure and two computational methods for the estimation are proposed: a Markov chain Monte Carlo algorithm and a scalable Bayesian EM algorithm. Being based on the spike-and-slab framework for fast posterior mode identification, the latter enables Bayesian data analysis of matrix-valued time series at large scales. The theoretical properties, comparative performance, and computational efficiency of the proposed model is investigated through simulated examples and an application to a panel of country economic indicators.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.4230/LIPIcs.SoCG.2023.57
