skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: On the connection between least squares, regularization, and classical shadows
Classical shadows (CS) offer a resource-efficient means to estimate quantum observables, circumventing the need for exhaustive state tomography. Here, we clarify and explore the connection between CS techniques and least squares (LS) and regularized least squares (RLS) methods commonly used in machine learning and data analysis. By formal identification of LS and RLS ``shadows'' completely analogous to those in CS---namely, point estimators calculated from the empirical frequencies of single measurements---we show that both RLS and CS can be viewed as regularizers for the underdetermined regime, replacing the pseudoinverse with invertible alternatives. Through numerical simulations, we evaluate RLS and CS from three distinct angles: the tradeoff in bias and variance, mismatch between the expected and actual measurement distributions, and the interplay between the number of measurements and number of shots per measurement.Compared to CS, RLS attains lower variance at the expense of bias, is robust to distribution mismatch, and is more sensitive to the number of shots for a fixed number of state copies---differences that can be understood from the distinct approaches taken to regularization. Conceptually, our integration of LS, RLS, and CS under a unifying ``shadow'' umbrella aids in advancing the overall picture of CS techniques, while practically our results highlight the tradeoffs intrinsic to these measurement approaches, illuminating the circumstances under which either RLS or CS would be preferred, such as unverified randomness for the former or unbiased estimation for the latter.  more » « less
Award ID(s):
2241298 2409701
PAR ID:
10609165
Author(s) / Creator(s):
; ;
Publisher / Repository:
Quantum
Date Published:
Journal Name:
Quantum
Volume:
8
ISSN:
2521-327X
Page Range / eLocation ID:
1455
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Navigation problems are generally solved applying least-squares (LS) adjustments. Techniques based on LS can be shown to perform optimally when the system noise is Gaussian distributed and the parametric model is accurately known. Unfortunately, real world problems usually contain unexpectedly large errors, so-called outliers, that violate the noise model assumption, leading to a spoiled solution estimation. In this work, the framework of robust statistics is explored to provide robust solutions to the global navigation satellite systems (GNSS) single point positioning (SPP) problem. Considering that GNSS observables may be contaminated by erroneous measurements, we survey the most popular approaches for robust regression (M-, S-, and MM-estimators) and how they can be adapted into a general methodology for robust GNSS positioning. We provide both theoretical insights and validation over experimental datasets, which serves in discussing the robust methods in detail. 
    more » « less
  2. In this paper, we study the impact of the presence of byzantine sensors on the reduced-rank linear least squares (LS) estimator. A sensor network with N sensors makes observations of the physical phenomenon and transmits them to a fusion center which computes the LS estimate of the parameter of interest. It is well-known that rank reduction exploits the bias-variance trade-off in the full-rank estimator by putting higher priority on highly informative content of the data. The low-rank LS estimator is constructed using this highly informative content, while the remaining data can be discarded without affecting the overall performance of the estimator. We consider the scenario where a fraction of the N sensors are subject to data falsification attack from byzantine sensors, wherein an intruder injects a higher noise power (compared to the unattacked sensors) to the measurements of the attacked sensors. Our main contribution is an analytical characterization of the impact of data falsification attack of the above type on the performance of reduced-rank LS estimator. In particular, we show how optimally prioritizing the highly informative content of the data gets affected in the presence of attacks. A surprising result is that, under sensor attacks, when the elements of the data matrix are all positive the error performance of the low rank estimator experiences a phenomenon wherein the estimate of the mean-squared error comprises negative components. A complex nonlinear programming-based recipe is known to exist that resolves this undesirable effect; however, the phenomenon is oftentimes considered very objectionable in the statistical literature. On the other hand, to our advantage this effect can serve to detect cyber attacks on sensor systems. Numerical results are presented to complement the theoretical findings of the paper. 
    more » « less
  3. In order to secure wireless communications, we consider the usage of physical-layer security (PLS) mechanisms (i.e., coding for secrecy mechanisms) combined with self-interference generation. We present a prototype implementation of a scrambled coding for secrecy mechanisms with interference generation by the legitimate receiver and the cancellation of the effect of self-interference (SI). Regarding the SI cancellation, four state-of-the-art algorithms were considered: Least mean square (LMS), normalized least mean square (NLMS), recursive least squares (RLS) and QR decomposition recursive least squares (QRDRLS). The prototype implementation is performed in real-world software-defined radio (SDR) devices using GNU-Radio, showing that the LMS outperforms all other algorithms considered (NLMS, RLS and QRDRLS), being the best choice to use in this situation (SI cancellation). It was also shown that it is possible to secure communication using only noise generation by the legitimate receiver, though a variation of the packet loss rate (PLR) and the bit error rate (BER) gaps is observed when moving from the fairest to an advantageous or a disadvantageous scenario. Finally, when noise generation was combined with the adapted scrambled coding for secrecy with a hidden key scheme, a noteworthy security improvement was observed resulting in an increased BER for Eve with minor interference to Bob. 
    more » « less
  4. null (Ed.)
    In this paper, a detection and localization technique based on dual State and Parameter Estimation (SE and PE respectively) for series dc arc faults is presented. Detection of series arc faults in dc microgrids is challenging due to its low fault current. By using the available set of sensor measurement data over a period of time, a Least Squares (LS) based SE algorithm estimates the dc microgrid's bus voltages and injection currents. Kalman Filter (KF) is then used to estimate the line conductances in the network, which are used to detect and localize (with respect to the faulted line) the series arc fault. Simulation results are presented with different case studies to demonstrate the robustness of the algorithm to normal operating conditions and different number and placement of sensors. Finally, Control Hardware in the Loop (CHIL) results are shown. 
    more » « less
  5. This paper addresses the problem of model-free reinforcement learning for Robust Markov Decision Process (RMDP) with large state spaces. The goal of the RMDP framework is to find a policy that is robust against the parameter uncertainties due to the mismatch between the simulator model and real-world settings. We first propose the Ro- bust Least Squares Policy Evaluation algorithm, which is a multi-step online model-free learning algorithm for policy evaluation. We prove the convergence of this algorithm using stochastic approximation techniques. We then propose Robust Least Squares Policy Iteration (RLSPI) algorithm for learning the optimal robust policy. We also give a general weighted Euclidean norm bound on the error (closeness to optimality) of the resulting policy. Finally, we demonstrate the performance of our RLSPI algorithm on some standard bench- mark problems. 
    more » « less