FINITE SAMPLE PERFORMANCE OF LEAST SQUARES ESTIMATION IN SUB-GAUSSIAN NOISE

In this paper we analyze the finite sample performance of the least squares estimator. In contrast to standard performance analysis which uses bounds on the mean square error together with asymptotic normality, our bounds are based on large deviation and concentration of measure results. This allows for accurate bounds on the tail of the estimator. We show the fast exponential convergence of the number of samples required to ensure accuracy with high probability. We analyze a sub-Gaussian setting with fixed or random mixing matrix of the least squares problem. We provide probability tail bounds on the L infinity norm of the error of the finite sample approximation of the true parameter. Our method is simple and uses simple analysis for L infinity type bounds of the estimation error. The tightness of the bound is studied through simulations.