Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recovery

This section is devoted to a review of the most relevant works. Before that we note that a heavy-tailed random variable in this work is formulated by the moment constraint $\mathbbm{E}|X|^{l}\leq M$ where $M$ is oftentimes regarded as absolute constant and $l$ is some fixed small scalar (specifically, $l\leq 4$ in the present paper).

The remainder of this paper is structured as follows. We provide the notation and preliminaries in Section 2. We present the first set of main results (concerning the (near) optimal guarantees for three estimation problems under quantized heavy-tailed data) in Section 3. Our second set of results (concerning covariate quantization and uniform recovery in quantized compressed sensing) is then presented in Section 4. To corroborate our theory, numerical results on synthetic data are reported in Section 5. We give some remarks to conclude the paper in Section 6. All the proofs are postponed to the Appendices.

Let $X$ be a real random variable, we present some basic knowledge on the sub-Gaussian and sub-exponential random variable. Then we also precisely formulate the heavy-tailed distribution.

1) The sub-Gaussian norm is defined as $\|X\|_{\psi_{2}}=\inf\{t>0:\mathbbm{E}\exp(\frac{X^{2}}{t^{2}})\leq 2\}$. A random variable $X$ with finite $\|X\|_{\psi_{2}}$ is said to be sub-Gaussian. Analogously to Gaussian variable, a sub-Gaussian random variable exhibits an exponentially-decaying probability tail and satisfies a moment constraint:

	$$\displaystyle\mathbbm{P}(|X|\geq t)\leq 2\exp\left(-\frac{ct^{2}}{\|X\|_{\psi_{2}}^{2}}\right);$$		(2.1)
	$$\displaystyle(\mathbbm{E}|X|^{p})^{1/p}\leq C\|X\|_{\psi_{2}}\sqrt{p},~{}\forall~{}p\geq 1.$$		(2.2)

Note that these two properties can also define $\|\cdot\|_{\psi_{2}}$ up to multiplicative constant, e.g., $\|X\|_{\psi_{2}}\asymp\sup_{p\geq 1}\frac{(\mathbbm{E}|X|^{p})^{1/p}}{\sqrt{p}}$ (see [92, Prop. 2.5.2]). For a $d$-dimensional random vector $\bm{x}$ we define its sub-Gaussian norm as $\|\bm{x}\|_{\psi_{2}}=\sup_{\bm{v}\in\mathbb{S}^{d-1}}\|\bm{v}^{\top}\bm{x}\|_{\psi_{2}}$.

2) The sub-exponential norm is defined as $\|X\|_{\psi_{1}}=\inf\{t>0:\mathbbm{E}\exp(\frac{|X|}{t})\leq 2\}$, and $X$ is sub-exponential if $\|X\|_{\psi_{1}}<\infty$. The sub-exponential $X$ satisfies the following properties:

	$$\displaystyle\mathbbm{P}(|X|\geq t)\leq 2\exp\left(-\frac{ct}{\|X\|_{\psi_{1}}}\right);$$
	$$\displaystyle(\mathbbm{E}|X|^{p})^{1/p}\leq C\|X\|_{\psi_{1}}p,~{}\forall~{}p\geq 1.$$		(2.3)

To relate $\|.\|_{\psi_{1}}$ and $\|.\|_{\psi_{2}}$ one has $\|XY\|_{\psi_{2}}\leq\|X\|_{\psi_{1}}\|Y\|_{\psi_{1}}$ [92, Lem. 2.7.7].

3) In contrast to the moment constraints in (2.2) and (2.3), heavy-tailed distributions in this work are only assumed to satisfy bounded moments of some small order no greater than $4$, formulated for a random variable $X$ as $\mathbbm{E}|X|^{l}\leq M$ for some $M>0$ and $l\in(0,4]$. Following [58, Def. 2.4, 2.5], we consider the following two moment assumptions for a heavy-tailed random vector $\bm{x}\in\mathbb{R}^{d}$ (again, $M>0$, $l\in(0,4]$):

• •

  Marginal Moment Constraint. The weaker assumption that constraints the moment of each coordinate, formulated by $\sup_{i\in[d]}\mathbbm{E}|x_{i}|^{l}\leq M$.

• •

  Joint Moment Constraint. The stronger assumption that constraints the moments “toward all directions $\bm{v}\in\mathbb{S}^{d-1}$,” formulated by $\sup_{\bm{v}\in\mathbb{S}^{d-1}}\mathbbm{E}|\bm{v}^{\top}\bm{x}|^{l}\leq M$.

In this part, we describe the dithered uniform quantizer and its properties in detail. We also specify the choices of random dither in this work.

1) We first provide the detailed procedure of dithered quantization and its general property. Let $\bm{x}\in\mathbb{R}^{N}$ be the input signal with dimension $N\geq 1$ whose entries may be random and dependent. Independent of $\bm{x}$, we generate the random dither $\bm{\tau}\in\mathbb{R}^{N}$ with i.i.d. entries from some distribution,⁸⁸8Throughout this work, we suppose that a random dither is drawn independent of anything else (particularly, the signal to be quantized and other dithers), and the dither has i.i.d. entries if it is a vector. and then quantize $\bm{x}$ to $\bm{\dot{x}}=\mathcal{Q}_{\Delta}(\bm{x}+\bm{\tau})$. Following [41], we refer to $\bm{w}:=\bm{\dot{x}}-(\bm{x}+\bm{\tau})$ as the quantization error, and $\bm{\xi}:=\bm{\dot{x}}-\bm{x}$ as the quantization noise. The principal properties of dithered quantization are provided in Theorem 1.

We note that Theorem 1 serves as the cornerstone for our analysis on the dithered uniform quantizer; for instance, (a) allows for applications of concentration inequalities in our analyses, and (b) inspires us to develop a covariance matrix estimator from quantized samples. The take-home message is that, adding appropriate dither before quantization can make the quantization error and quantization noise behave in a statistically nice manner. For example, the elementary form of Theorem 1(a) is that under a dither $\tau_{i}$ satisfying the condition there, the quantization noise $\mathcal{Q}_{\Delta}(x_{i}+\tau_{i})-(x_{i}+\tau_{i})$ follows $\mathscr{U}([-\frac{\Delta}{2},\frac{\Delta}{2}])$ under any given scalar $x_{i}$ [41, Lem. 1].

2) We use uniform dither for quantization of the response in compressed sensing and matrix completion. More specifically, under $\Delta>0$, we adopt the uniform dither $\tau_{k}\sim\mathscr{U}([-\frac{\Delta}{2},\frac{\Delta}{2}])$ for the response $y_{k}\in\mathbb{R}$, which is also a common choice in previous works (e.g., [89, 94, 32, 50]). For $Y\sim\mathscr{U}([-\frac{\Delta}{2},\frac{\Delta}{2}])$, it can be calculated that

$$\mathbbm{E}(\exp(\mathsf{i}uY))=\int_{-\Delta/2}^{\Delta/2}~{}\frac{1}{\Delta}\big{(}\cos(ux)+\mathsf{i}\sin(ux)\big{)}~{}\mathrm{d}x=\frac{2}{\Delta u}\sin\Big{(}\frac{\Delta u}{2}\Big{)},$$

(2.4)

and hence $\mathbbm{E}(\exp(\mathsf{i}\frac{2\pi l}{\Delta}Y))=0$ holds for all non-zero integer $l$. Therefore, the benefit of using $\tau_{k}\sim\mathscr{U}([-\frac{\Delta}{2},\frac{\Delta}{2}])$ is that the quantization errors $w_{k}=\mathcal{Q}_{\Delta}(y_{k}+\tau_{k})-(y_{k}+\tau_{k})$ i.i.d. follow $\mathscr{U}([-\frac{\Delta}{2},\frac{\Delta}{2}])$, and are independent of $\{y_{k}\}$.

3) We use triangular dither for quantization of the covariate, i.e., the sample in covariance estimation or the covariate in comprssed sensing. Particularly, when considering the uniform quantizer $\mathcal{Q}_{\Delta}(.)$ for the covariate $\bm{x}_{k}\in\mathbb{R}^{d}$, we adopt the dither $\bm{\tau}_{k}\sim\mathscr{U}([-\frac{\Delta}{2},\frac{\Delta}{2}]^{d})+\mathscr{U}([-\frac{\Delta}{2},\frac{\Delta}{2}]^{d})$,¹⁰¹⁰10An equivalent statement is that entries of $\bm{\tau}_{k}$ are i.i.d. distributed as $\mathscr{U}\big{(}\big{[}-\frac{\Delta}{2},\frac{\Delta}{2}\big{]}\big{)}+\mathscr{U}\big{(}\big{[}-\frac{\Delta}{2},\frac{\Delta}{2}\big{]}\big{)}$. The equivalence can be clearly seen by comparing the joint probability density functions. which is the sum of two independent $\mathscr{U}([-\frac{\Delta}{2},\frac{\Delta}{2}]^{d})$ and referred to as a triangular dither [41]. Simple calculations verify that the triangular dither respects not only the condition in Theorem 1(a), but also the one in Theorem 1(b) with $p=2$; specifically, let $Y=Y_{1}+Y_{2}$ where $Y_{1}$ and $Y_{2}$ are independent and follow $\mathscr{U}\big{(}\big{[}-\frac{\Delta}{2},\frac{\Delta}{2}\big{]}\big{)}$, and let $Z\sim\mathscr{U}\big{(}\big{[}-\frac{\Delta}{2},\frac{\Delta}{2}\big{]}\big{)}$ be independent of $Y$, then based on (2.4), we know $f(u)=\mathbbm{E}(\exp(\mathsf{i}uY))=\big{[}\frac{2}{\Delta u}\sin\frac{\Delta u}{2}\big{]}^{2}$ satisfies $f(\frac{2\pi l}{\Delta})=0$, and $g(u)=\mathbbm{E}(\exp(\mathsf{i}uY))\mathbbm{E}(\exp(\mathsf{i}uZ))=\big{[}\frac{2}{\Delta u}\sin\frac{\Delta u}{2}\big{]}^{3}$ satisfies $g^{\prime\prime}(\frac{2\pi l}{\Delta})=0$, where $l$ is any non-zero integer. Thus, at the cost of a dithering variance larger than uniform dither, the triangular dither brings the additional nice property of signal-independent variance for the quantization noise — $\mathbbm{E}(\xi_{ki}^{2})=\frac{1}{4}\Delta^{2}$, where $\xi_{ki}$ is the $i$-th entry of $\bm{\xi}_{k}=\mathcal{Q}_{\Delta}(\bm{x}_{k}+\bm{\tau}_{k})-(\bm{x}_{k}+\bm{\tau}_{k})$.

To the best of our knowledge, the triangular dither is new to the literature of quantized compressed sensing. We will explain its necessity if covariance estimation is involved. This is also complemented by numerical simulation (see Figure 5(a)).

Given $\mathscr{X}:=\{\bm{x}_{1},...,\bm{x}_{n}\}$ as i.i.d. copies of a zero-mean random vector $\bm{x}\in\mathbb{R}^{d}$, one often encounters the covariance matrix estimation problem, i.e., to estimate $\bm{\Sigma^{\star}}=\mathbbm{E}(\bm{x}\bm{x}^{\top})$. This estimation problem is of fundamental importance in multivariate analysis and has attracted much research interest (e.g., [12, 11, 13, 4]). However, the practically useful setting (e.g., in a massive MIMO system [95]) where the samples undergo certain quantization process remains under-developed, for which we are only aware of the 1-bit quantization results in [31, 21]. This setting poses the problem of quantized covariance matrix estimation (QCME), in which one aims to design quantization scheme for $\bm{x}_{k}$ that allows for accurate estimation of $\bm{\Sigma^{\star}}$ only based on the quantized samples. We consider heavy-tailed $\bm{x}_{k}$ that possesses bounded fourth moments either marginally or jointly, but note that our estimation methods and theoretical results appear to be new even for sub-Gaussian $\bm{x}_{k}$ (Remark 1).

As introduced before, we overcome the heavy-tailedness of $\bm{x}_{k}$ by a data truncation step, i.e., we first truncate $\bm{x}_{k}$ to $\bm{\widetilde{x}}_{k}$ in order to make the outliers less influential. Here, we defer the precise definition of $\bm{\widetilde{x}}_{k}$ to concrete results because it should be well suited to the error metric. After the truncation, we dither and quantize $\bm{\widetilde{x}}_{k}$ to $\bm{\dot{x}}_{k}=\mathcal{Q}_{\Delta}(\bm{\widetilde{x}}_{k}+\bm{\tau}_{k})$ with the triangular dither $\bm{\tau}_{k}\sim\mathscr{U}([-\frac{\Delta}{2},\frac{\Delta}{2}]^{d})+\mathscr{U}([-\frac{\Delta}{2},\frac{\Delta}{2}]^{d})$. Different from the uniform dither adopted in the literature (e.g., [21, 89, 94, 32, 50]), first let us explain our choice of triangular dither. Recall that the quantization noise and quantization error are respectively defined as $\bm{\xi}_{k}:=\bm{\dot{x}}_{k}-\bm{\widetilde{x}}_{k}$ and $\bm{w}_{k}:=\bm{\dot{x}}_{k}-\bm{\widetilde{x}}_{k}-\bm{\tau}_{k}$, thus giving $\bm{\xi}_{k}=\bm{\tau}_{k}+\bm{w}_{k}$. Under uniform dither or triangular dither, $\bm{w}_{k}$ is independent of $\bm{\widetilde{x}}_{k}$ and follows $\mathscr{U}([-\frac{\Delta}{2},\frac{\Delta}{2}]^{d})$ (see Section 2.2), thus allowing us to calculate that

	$\displaystyle\mathbbm{E}(\bm{\dot{x}}_{k}\bm{\dot{x}}_{k}^{\top})$	$\displaystyle=\mathbbm{E}\big{(}(\bm{\widetilde{x}}_{k}+\bm{\xi}_{k})(\bm{\widetilde{x}}_{k}+\bm{\xi}_{k})^{\top}\big{)}$		(3.1)
		$\displaystyle=\mathbbm{E}(\bm{\widetilde{x}}_{k}\bm{\widetilde{x}}_{k}^{\top})+\mathbbm{E}(\bm{\widetilde{x}}_{k}\bm{\xi}_{k}^{\top})+\mathbbm{E}(\bm{\xi}_{k}\bm{\widetilde{x}}_{k}^{\top})+\mathbbm{E}(\bm{\xi}_{k}\bm{\xi}_{k}^{\top})$
		$\displaystyle\stackrel{{\scriptstyle(i)}}{{=}}\mathbbm{E}(\bm{\widetilde{x}}_{k}\bm{\widetilde{x}}_{k}^{\top})+\mathbbm{E}(\bm{\xi}_{k}\bm{\xi}_{k}^{\top}).$

Note that $(i)$ is because $\mathbbm{E}(\bm{\xi}_{k}\bm{\widetilde{x}}_{k}^{\top})=\mathbbm{E}(\bm{\tau}_{k}\bm{\widetilde{x}}_{k}^{\top})+\mathbbm{E}(\bm{w}_{k}\bm{\widetilde{x}}_{k}^{\top})=\mathbbm{E}(\bm{\tau}_{k})\mathbbm{E}(\bm{\widetilde{x}}_{k}^{\top})+\mathbbm{E}(\bm{w}_{k})\mathbbm{E}(\bm{\widetilde{x}}_{k}^{\top})=0$, due to the previously noted fact that $\bm{\tau}_{k}$ and $\bm{w}_{k}$ are independent of $\bm{\widetilde{x}}_{k}$ and zero-mean. While with suitable choice of the truncation threshold $\mathbbm{E}(\bm{\widetilde{x}}_{k}\bm{\widetilde{x}}_{k}^{\top})$ is expected to well approximate $\bm{\Sigma^{\star}}$, the remaining $\mathbb{E}(\bm{\xi}_{k}\bm{\xi}_{k}^{\top})$ gives rise to constant bias. To address the issue, a straightforward idea is to remove the bias, which requires the full knowledge on $\mathbbm{E}(\bm{\xi}_{k}\bm{\xi}_{k}^{\top})$, i.e., the covariance matrix of the quantization noise. For $i\neq j$, because $\bm{\tau}_{k}$, $\bm{w}_{k}\sim\mathscr{U}([-\frac{\Delta}{2},\frac{\Delta}{2}]^{d})$ and $\mathbbm{E}(w_{ki}\tau_{kj})=\mathbbm{E}_{\widetilde{x}_{ki}}(\mathbbm{E}[w_{ki}\tau_{kj}|\widetilde{x}_{ki}])=0$ (note that conditionally on $\widetilde{x}_{ki}$, $w_{ki}=\mathcal{Q}_{\Delta}(\widetilde{x}_{ki}+\tau_{ki})-(\widetilde{x}_{ki}+\tau_{ki})$ and $\tau_{kj}$ are independent), we have

		$\displaystyle\mathbbm{E}(\xi_{ki}\xi_{kj})=\mathbbm{E}\big{(}(w_{ki}+\tau_{ki})(w_{kj}+\tau_{kj})\big{)}$
		$\displaystyle=\mathbbm{E}(w_{ki}w_{kj})+\mathbbm{E}(w_{ki}\tau_{kj})+\mathbbm{E}(\tau_{ki}w_{kj})+\mathbbm{E}(\tau_{ki}\tau_{kj})=0,$

showing that $\mathbbm{E}(\bm{\xi}_{k}\bm{\xi}_{k}^{\top})$ is diagonal. Moreover, under triangular dither the $i$-th diagonal entry is also known as $\mathbbm{E}|\xi_{ki}|^{2}=\frac{\Delta^{2}}{4}$, see Section 2.2. Taken collectively, we arrive at

$$\mathbbm{E}(\bm{\xi}_{k}\bm{\xi}_{k}^{\top})=\frac{\Delta^{2}}{4}\bm{I}_{d};$$

(3.2)

Based on (3.1) we thus propose the following estimator

$$\bm{\widehat{\Sigma}}=\frac{1}{n}\sum_{k=1}^{n}\bm{\dot{x}}_{k}\bm{\dot{x}}_{k}^{\top}-\frac{\Delta^{2}}{4}\bm{I}_{d},$$

(3.3)

which is the sample covariance of the quantized sample $\dot{\mathscr{X}}:=\{\bm{\dot{x}}_{1},...,\bm{\dot{x}}_{n}\}$ followed by a correction step. On the other hand, the reason why the standard uniform dither is not suitable for QCME becomes self-evident — the diagonal of $\mathbbm{E}(\bm{\xi}_{k}\bm{\xi}_{k}^{\top})$ remains unknown¹¹¹¹11It depends on the input signal, see [41, Page 3]. and hence there is no hope to precisely remove the bias.

We are now ready to present error bounds for $\bm{\widehat{\Sigma}}$ under max-norm, operator norm. We will also investigate the high-dimensional setting by assuming sparse structure of $\bm{\Sigma^{\star}}$, for which we propose a thresholding estimator. More concretely, our first result provides the error rate under $\|\cdot\|_{\infty}$, in which we assume $\bm{x}_{k}$ satisfies the marginal fourth moment constraint and utilize an element-wise truncation $\bm{\widetilde{x}}_{k}=\mathscr{T}_{\zeta}(\bm{x}_{k})$.

Notably, despite the heavy-tailedness and quantization, the estimator achieves an element-wise rate $O(\sqrt{\frac{\log d}{n}})$ coincident with the one for sub-Gaussian case. One can clearly position quantization level $\Delta$ in the multiplicative factor $\mathscr{L}=\sqrt{M}+\Delta^{2}$. Thus, the information loss incurred by quantization is inessential in that it does not affect the key scaling law but only slightly worsens the leading factor. These remarks on the (near) optimality and the information loss incurred by quantization remain valid in our subsequent theorems.

Our next result concerns the operator norm estimation error, under which we impose a stronger joint moment constraint on $\bm{x}_{k}$ and truncate $\bm{x}_{k}$ regarding $\ell_{4}$-norm, i.e., $\bm{\check{x}_{k}}=\frac{\bm{x}_{k}}{\|\bm{x}_{k}\|_{4}}\min\{\|\bm{x}_{k}\|_{4},\zeta\}$ for some threshold $\zeta$. After the dithered uniform quantization, we still define the estimator as (3.3).

The operator norm error rate in Theorem 3 is near minimax optimal, e.g., compared to the lower bound in [35, Thm. 7], which states that for any estimator $\bm{\widehat{\Sigma}}$ of the positive semi-definite matrix $\bm{\Sigma^{\star}}$ based on i.i.d. zero-mean $\{\bm{x}_{k}\}_{k=1}^{n}$ with covariance matrix $\bm{\Sigma^{\star}}$, there exists some $\bm{v}_{0}\in\mathbb{S}^{d-1}$ such that $\mathbbm{P}\big{(}\|\bm{\widehat{\Sigma}}-\bm{\Sigma^{\star}}\|_{op}\geq\frac{1}{48}\sqrt{\frac{6d}{n}}\big{)}\geq\frac{1}{3}$, where $\bm{\Sigma^{\star}}=\bm{I}_{d}+\bm{v}_{0}\bm{v}_{0}^{\top}$. Again, the quantization only affects the multiplicative factor $\mathscr{L}$. Nevertheless, one still needs (at least) $n\gtrsim d$ to achieve small operator norm error. In fact, in a high-dimensional setting where $d$ may exceed $n$, even the sample covariance $\frac{1}{n}\sum_{k=1}^{n}\bm{x}_{k}\bm{x}_{k}^{\top}$ for sub-Gaussian zero-mean $\bm{x}_{k}$ may have extremely bad performance. To achieve small operator norm error in a high-dimensional regime, we resort to additional structure on $\bm{\Sigma^{\star}}$, and specifically we use column-wise sparsity as an example, which corresponds to the situations where dependencies among different coordinates are weak. Based on the estimator in Theorem 2, we further invoke a thresholding regularization [4, 12] to promote sparsity.

Notably, our estimator $\bm{\widehat{\Sigma}}_{s}$ achieves minimax rates $O\big{(}s\sqrt{\frac{\log d}{n}}\big{)}$ under operator norm, e.g., compared to the minimax lower bound derived in [12, Thm. 2], which states that (under some regular scaling) for any covariance estimator $\bm{\Sigma}_{es}$ based on $n$ i.i.d. samples of $\mathcal{N}(\bm{\mu},\bm{\Sigma}^{\star})$ where $\bm{\Sigma}^{\star}$ is the true covariance matrix, there exists some covariance matrix $\bm{\Sigma^{\star}}$ with $s$-sparse columns such that $\mathbbm{E}\|\bm{\Sigma}_{es}-\bm{\Sigma}^{\star}\|_{op}^{2}\gtrsim s^{2}\frac{\log d}{n}$.

To analyse the thresholding estimator, our proof resembles the ones developed in prior works (e.g., [12]) but requires more efforts like bounding the additional bias terms arising from the data truncation and quantization. We also point out that the results for the full-data unquantized regime immediately follow by setting $\Delta=0$, thus Theorems 2-3 represent the strict extension of [35, Sect. 4], and Theorem 4 complements [35] with a high-dimensional sparse setting.

We consider the linear model

$$y_{k}=\bm{x}_{k}^{\top}\bm{\theta^{\star}}+\epsilon_{k},~{}k=1,...,n,$$

(3.4)

where $\bm{x}_{k}$s are the covariates, $y_{k}$s are responses, $\bm{\theta^{\star}}$ is the sparse signal in compressed sensing or sparse parameter vector in high-dimensional linear regression that we want to estimate. In the quantized compressed sensing (QCS) problem, we are interested in developing quantization scheme for $(\bm{x}_{k},y_{k})$s $($mainly for $y_{k}$ in prior works$)$ that enables accurate recovery of $\bm{\theta^{\star}}$ based on the quantized data.

In spite of the same mathematical formulation, there are some important differences between compressed sensing and sparse linear regression that we should clarify first. Specifically, different from sensing vectors in compressed sensing that are generated by some analog measuring device and can oftentimes be designed, $\bm{x}_{k}$s in sparse linear regression represent the sample data from certain datasets that are believed to affect the responses $y_{k}$s through (3.4). While the sparsity of $\bm{\theta^{\star}}$ is arguably the most classical signal structure for compressed sensing, due to good interpretability it is also commonly adopted to achieve dimension reduction in high-dimensional statistics. In this work, we are interested in both problem settings. Thus, we do not adopt the isotropic convention (i.e., $\mathbbm{E}(\bm{x}_{k}\bm{x}_{k}^{\top})=\bm{I}_{d}$) from compressed sensing but instead deal with $\bm{x}_{k}$ having general unknown covariance matrix. While the study of quantization and heavy-tailed noise is meaningful in both settings, we note that some of our subsequent results are mainly of interest to the specific sensing or regression problem. For instance, the heavy-tailed covariate considered in Theorem 6 is primarily motivated by the regression setting, in which $\bm{x}_{k}$ may come from a dataset that exhibits much heavier tail than sub-Gaussian data. Moreover, as will be elaborated in Section 4 when appropriate, our subsequent results on covariate quantization (resp., uniform signal recovery guarantee) may prove more useful to the regression problem (resp., compressed sensing problem).

To fix idea, we assume that $\bm{x}_{k}$s are i.i.d. drawn from some multi-variate distribution, $\epsilon_{k}$s are i.i.d. statistical noise independent of the $\bm{x}_{k}$s, and we truncate $y_{k}$ to $\widetilde{y}_{k}=\mathscr{T}_{\zeta_{y}}(y_{k})$ and then quantize it to $\dot{y}_{k}=\mathcal{Q}_{\Delta}(\widetilde{y}_{k}+\tau_{k})$ with uniform dither $\tau_{k}\sim\mathscr{U}([-\frac{\Delta}{2},\frac{\Delta}{2}])$. Under these statistical assumptions and dithered quantization, near optimal recovery guarantees have been established in [89, 94] for the regime where both $\bm{x}_{k}$ and $\epsilon_{k}$ are drawn from sub-Gaussian distributions (hence the truncation is not needed). In contrast, our focus is on quantization of heavy-tailed data. Particularly, we always assume that the noise $\epsilon_{k}$s are i.i.d. drawn from some heavy-tailed distribution, resulting in heavy-tailed responses. We will separately deal with the case of sub-Gaussian covariate and a more challenging situation where $\bm{x}_{k}$s are also heavy-tailed.

To estimate the sparse $\bm{\theta^{\star}}$, a classical approach is via the regularized M-estimator known as Lasso [90, 70, 72]

$\displaystyle\mathop{\arg\min}\limits_{\bm{\theta}}~{}\frac{1}{2n}\sum_{k=1}^{n}(y_{k}-\bm{x}_{k}^{\top}\bm{\theta})^{2}+\lambda\|\bm{\theta}\|_{1},$

whose objective combines the $\ell_{2}$-loss for data fidelity and $\ell_{1}$-norm that encourages sparsity. Because we can only access the quantized data $(\bm{x}_{k},\dot{y}_{k})$ (or even $(\bm{\dot{x}}_{k},\dot{y}_{k})$ if covariate quantization is involved, see Section 4), the main issue lies in the $\ell_{2}$-loss $\frac{1}{2n}\sum_{k=1}^{n}(y_{k}-\bm{x}_{k}^{\top}\bm{\theta})^{2}$ that requires the unquantized data $(\bm{x}_{k},y_{k})$. To resolve the issue, we calculate the expected $\ell_{2}$-loss:

	$\displaystyle\mathbbm{E}(y_{k}-\bm{x}_{k}^{\top}\bm{\theta})^{2}$	$\displaystyle\stackrel{{\scriptstyle(i)}}{{=}}\bm{\theta}^{\top}\mathbbm{E}(\bm{x}_{k}\bm{x}_{k}^{\top})\bm{\theta}-2\mathbbm{E}(y_{k}\bm{x}_{k})^{\top}\bm{\theta}:$		(3.5)
		$\displaystyle\stackrel{{\scriptstyle(ii)}}{{=}}\bm{\theta}^{\top}\bm{\Sigma^{\star}}\bm{\theta}-2\bm{\Sigma}_{y\bm{x}}^{\top}\bm{\theta},$

where $(i)$ holds up to an inessential constant $\mathbbm{E}|y_{k}|^{2}$, and in $(ii)$ we let $\bm{\Sigma^{\star}}:=\mathbbm{E}(\bm{x}_{k}\bm{x}_{k}^{\top})$, $\bm{\Sigma}_{y\bm{x}}=\mathbbm{E}(y_{k}\bm{x}_{k})$. This inspires us to generalize the $\ell_{2}$ loss to $\frac{1}{2}\bm{\theta}^{\top}\bm{Q}\bm{\theta}-\bm{b}^{\top}\bm{\theta}$ and consider the following program

$$\bm{\widehat{\theta}}=\mathop{\arg\min}\limits_{\bm{\theta}\in\mathcal{S}}~{}\frac{1}{2}\bm{\theta}^{\top}\bm{Q}\bm{\theta}-\bm{b}^{\top}\bm{\theta}+\lambda\|\bm{\theta}\|_{1}.$$

(3.6)

Compared to (3.5) we will use $(\bm{Q},\bm{b})$ that well approximates $(\bm{\Sigma^{\star}},\bm{\Sigma}_{y\bm{x}})$, and we also introduce the constraint $\bm{\theta}\in\mathcal{S}$ to allow more flexibility. It is important to note that this is the general strategy in this work to design estimators in different QCS settings, see more discussions in Remark 3.

The next theorem is concerned with QCS under sub-Gaussian covariate but heavy-tailed response. Note that the heavy-tailedness of $y_{k}$ stems from the noise distribution assumed to have bounded $2+\nu$ moment ($\nu=2(l-1)>0$ in the theorem statement), but following [35, 21, 97] we directly impose the moment constraint on the response.