skip to main content

Title: Fast state tomography with optimal error bounds

Projected least squares is an intuitive and numerically cheap technique for quantum state tomography: compute the least-squares estimator and project it onto the space of states. The main result of this paper equips this point estimator with rigorous, non-asymptotic convergence guarantees expressed in terms of the trace distance. The estimator’ssample complexityis comparable to the strongest convergence guarantees available in the literature and—in the case of the uniform POVM—saturates fundamental lower bounds. Numerical simulations support these competitive features.

more » « less
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
IOP Publishing
Date Published:
Journal Name:
Journal of Physics A: Mathematical and Theoretical
Page Range / eLocation ID:
Article No. 204001
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Summary

    We present a certainty equivalence‐based adaptive boundary control scheme with a regulation‐triggered batch least‐squares identifier, for a heterodirectional transport partial differential equation‐ordinary differential equation (PDE‐ODE) system where the transport speeds of both transport PDEs are unknown. We use a nominal controller which is fed piecewise‐constant parameter estimates from an event‐triggered parameter update law that applies a least‐squares estimator to data “batches” collected over time intervals between the triggers. A parameter update is triggered by an observed growth in the norm of the PDE state. The proposed triggering‐based adaptive control guarantees: (1) the absence of a Zeno phenomenon; (2) parameter estimates are convergent to the true values in finite time (from most initial conditions); (3) exponential regulation of the plant states to zero. The effectiveness of the proposed design is verified by a numerical example.

    more » « less
  2. Abstract

    We consider the nonparametric estimation of an S-shaped regression function. The least squares estimator provides a very natural, tuning-free approach, but results in a non-convex optimization problem, since the inflection point is unknown. We show that the estimator may nevertheless be regarded as a projection onto a finite union of convex cones, which allows us to propose a mixed primal-dual bases algorithm for its efficient, sequential computation. After developing a projection framework that demonstrates the consistency and robustness to misspecification of the estimator, our main theoretical results provide sharp oracle inequalities that yield worst-case and adaptive risk bounds for the estimation of the regression function, as well as a rate of convergence for the estimation of the inflection point. These results reveal not only that the estimator achieves the minimax optimal rate of convergence for both the estimation of the regression function and its inflection point (up to a logarithmic factor in the latter case), but also that it is able to achieve an almost-parametric rate when the true regression function is piecewise affine with not too many affine pieces. Simulations and a real data application to air pollution modelling also confirm the desirable finite-sample properties of the estimator, and our algorithm is implemented in the R package Sshaped.

    more » « less
  3. This paper studies the asymptotic properties of the penalized least squares estimator using an adaptive group Lasso penalty for the reduced rank regression. The group Lasso penalty is defined in the way that the regression coefficients corresponding to each predictor are treated as one group. It is shown that under certain regularity conditions, the estimator can achieve the minimax optimal rate of convergence. Moreover, the variable selection consistency can also be achieved, that is, the relevant predictors can be identified with probability approaching one. In the asymptotic theory, the number of response variables, the number of predictors and the rank number are allowed to grow to infinity with the sample size. Copyright © 2016 John Wiley & Sons, Ltd.

    more » « less
  4. ABSTRACT Objectives:

    Environmental enteric dysfunction (EED) may inhibit growth and development in low‐ and middle‐income countries, but available assessment methodologies limit its study. In rural Bangladesh, we measured EED using the widely used lactulose mannitol ratio (L:M) test and a panel of intestinal and systemic health biomarkers to evaluate convergence among biomarkers and describe risk factors for EED.


    In 539 18‐month‐old children finishing participation in a randomized food supplementation trial, serum, stool, and urine collected after lactulose and mannitol dosing were analyzed for biomarkers of intestinal absorption, inflammation, permeability and repair, and systemic inflammation. EED scores for each participant were developed using principal component analysis and partial least squares regression. Associations between scores and L:M and with child sociodemographic and health characteristics were evaluated using regression analysis.


    EED prevalence (L:M > 0.07) was 39.0%; 60% had elevated acute phase proteins (C‐reactive protein >5 mg/L or α‐1 acid glycoprotein >100 mg/dL). Correlations between intestinal biomarkers were low, with the highest between myeloperoxidase and α‐1 antitrypsin (r= 0.33,P< 0.01), and biomarker values did not differ by supplementation history. A 1‐factor partial least squares model with L:M as the dependent variable explained only 8.6% of L:M variability. In adjusted models, L:M was associated with child sex and socioeconomic status index, whereas systemic inflammation was predicted mainly by recent illness, not EED.


    Impaired intestinal health is widespread in this setting of prevalent stunting, but a panel of serum and stool biomarkers demonstrated poor agreement with L:M. Etiologies of intestinal and systemic inflammation are likely numerous and complex in resource‐poor settings, underscoring the need for a better case definition with corresponding diagnostic methods to further the study of EED.

    more » « less
  5. We provide a computationally and statistically efficient estimator for the classical problem of trun-cated linear regression, where the dependent variabley=wTx+εand its corresponding vector ofcovariatesx∈Rkare only revealed if the dependent variable falls in some subsetS⊆R; otherwisethe existence of the pair(x,y)is hidden. This problem has remained a challenge since the earlyworks of Tobin (1958); Amemiya (1973); Hausman and Wise (1977); Breen et al. (1996), its appli-cations are abundant, and its history dates back even further to the work of Galton, Pearson, Lee,and Fisher Galton (1897); Pearson and Lee (1908); Lee (1914); Fisher (1931). While consistent es-timators of the regression coefficients have been identified, the error rates are not well-understood,especially in high-dimensional settings.Under a “thickness assumption” about the covariance matrix of the covariates in the revealed sample, we provide a computationally efficient estimator for the coefficient vectorwfromnre-vealed samples that attains`2errorO(√k/n), recovering the guarantees of least squares in thestandard (untruncated) linear regression setting. Our estimator uses Projected Stochastic Gradi-ent Descent (PSGD) on the negative log-likelihood of the truncated sample, and only needs ora-cle access to the setS, which may otherwise be arbitrary, and in particular may be non-convex.PSGD must be restricted to an appropriately defined convex cone to guarantee that the negativelog-likelihood is strongly convex, which in turn is established using concentration of matrices onvariables with sub-exponential tails. We perform experiments on simulated data to illustrate the accuracy of our estimator.As a corollary of our work, we show that SGD provably learns the parameters of single-layerneural networks with noisy Relu activation functions Nair and Hinton (2010); Bengio et al. (2013);Gulcehre et al. (2016), given linearly many, in the number of network parameters, input-outputpairs in the realizable setting. 
    more » « less