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
-
more » « less
Abstract We prove that 2-dimensional
Q -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 Bounded input delay frequently arises in discrete‐time linear systems. The standard predictor feedback design requires the exact knowledge of the delay. Such a requirement on the availability of the delay knowledge poses challenges in the design of robust control laws when only the knowledge of an upper bound of the delay is known. We propose such a design in this article. Based on the delay‐independent truncated predictor state feedback design, an observer‐based output feedback law is constructed that does not contain any explicit information of the delay. For a general, possibly exponentially unstable, discrete‐time linear system, the proposed output feedback law stabilizes the system as long as the delay does not exceed a certain amount. For the special case of systems with all the open‐loop poles on or inside the unit circle, a low gain feedback design is presented. This low gain design allows us to establish that, when all the open‐loop poles of a system are at
z = 1
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.4230/LIPIcs.SoCG.2023.57
