Breaking the waves: asymmetric random periodic features for low-bitrate kernel machines

• URL: http://arxiv.org/abs/2004.06560v3
• Date: Mon, 15 Mar 2021 10:57:05 GMT
• Title: Breaking the waves: asymmetric random periodic features for low-bitrate kernel machines
• Authors: Vincent Schellekens and Laurent Jacques
• Abstract summary: We introduce the general framework of asymmetric random periodic features, where the two signals of interest are observed through random periodic features. We prove uniform probabilistic error bounds holding for all signal pairs from an infinite low-complexity set.
• Score: 13.704881067616995
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many signal processing and machine learning applications are built from evaluating a kernel on pairs of signals, e.g. to assess the similarity of an incoming query to a database of known signals. This nonlinear evaluation can be simplified to a linear inner product of the random Fourier features of those signals: random projections followed by a periodic map, the complex exponential. It is known that a simple quantization of those features (corresponding to replacing the complex exponential by a different periodic map that takes binary values, which is appealing for their transmission and storage), distorts the approximated kernel, which may be undesirable in practice. Our take-home message is that when the features of only one of the two signals are quantized, the original kernel is recovered without distortion; its practical interest appears in several cases where the kernel evaluations are asymmetric by nature, such as a client-server scheme. Concretely, we introduce the general framework of asymmetric random periodic features, where the two signals of interest are observed through random periodic features: random projections followed by a general periodic map, which is allowed to be different for both signals. We derive the influence of those periodic maps on the approximated kernel, and prove uniform probabilistic error bounds holding for all signal pairs from an infinite low-complexity set. Interestingly, our results allow the periodic maps to be discontinuous, thanks to a new mathematical tool, i.e. the mean Lipschitz smoothness. We then apply this generic framework to semi-quantized kernel machines (where only one signal has quantized features and the other has classical random Fourier features), for which we show theoretically that the approximated kernel remains unchanged (with the associated error bound), and confirm the power of the approach with numerical simulations.

Related papers

• Inferring Kernel $ε$-Machines: Discovering Structure in Complex Systems [49.1574468325115]
  We introduce causal diffusion components that encode the kernel causal-state estimates as a set of coordinates in a reduced dimension space. We show how each component extracts predictive features from data and demonstrate their application on four examples.
  arXiv  Detail & Related papers  (2024-10-01T21:14:06Z)
• Universal spectra of noisy parameterized quantum circuits [1.2617078020344619]
  We implement parameterized circuits, which have been proposed as a means to generate random unitaries on a transmon platform. To retrieve the maps, a machine-learning assisted tomography is used. We find the spectrum of a map to be either an annulus or a disk depending on the circuit depth and detect an annulus-disk transition.
  arXiv  Detail & Related papers  (2024-05-19T17:36:55Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• On noise in swap ASAP repeater chains: exact analytics, distributions and tight approximations [9.32782060570252]
  Losses are one of the main bottlenecks for the distribution of entanglement in quantum networks. We analytically investigate the case of equally-spaced repeaters. We find exact analytic formulae for all moments of the fidelity up to 25 segments.
  arXiv  Detail & Related papers  (2024-04-10T16:24:51Z)
• Sampled Transformer for Point Sets [80.66097006145999]
  sparse transformer can reduce the computational complexity of the self-attention layers to $O(n)$, whilst still being a universal approximator of continuous sequence-to-sequence functions. We propose an $O(n)$ complexity sampled transformer that can process point set elements directly without any additional inductive bias.
  arXiv  Detail & Related papers  (2023-02-28T06:38:05Z)
• Partial randomized benchmarking [0.0]
  In randomized benchmarking of quantum logical gates, partial twirling can be used for simpler implementation, better scaling, and higher accuracy and reliability. We analyze such simplified, partial twirling and demonstrate that, unlike for the standard randomized benchmarking, the measured decay of fidelity is a linear combination of exponentials with different decay rates.
  arXiv  Detail & Related papers  (2021-11-07T22:15:11Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  We show that discretizations yielding consistent estimators have the property of invariance under coarse-graining' This result explains why combining differencing schemes for derivatives reconstruction and local-in-time inference approaches does not work for time series analysis of second or higher order differential equations.
  arXiv  Detail & Related papers  (2021-01-16T17:11:02Z)
• Fastest local entanglement scrambler, multistage thermalization, and a non-Hermitian phantom [0.0]
  We study random quantum circuits and their rate of producing bipartite entanglement. The problem is mapped to a Markovian process and proved that there are large spectral equivalence classes. We numerically demonstrate that the phenomenon occurs also in random circuits with non-optimal generic gates.
  arXiv  Detail & Related papers  (2021-01-14T13:11:29Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)
• How quantum evolution with memory is generated in a time-local way [0.0]
  Two approaches to dynamics of open quantum systems are Nakajima-Zwanzig and time-convolutionless quantum master equation. We show that the two are connected by a simple yet general fixed-point relation. This allows one to extract nontrivial relations between the two.
  arXiv  Detail & Related papers  (2020-02-17T20:10:49Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.