Abstract
Consistent reconstruction is a method for estimating a signal from a collection of linear measurements that have been corrupted by uniform noise. We prove upper bounds on general error moments for consistent reconstruction, and we establish general admissibility conditions on the sampling distributions used for consistent reconstruction. This extends previous work in Powell and Whitehouse (Found Comput Math 16:395–423, 2016) that addressed mean squared error in the setting of unit-norm sampling distributions.
Access provided by CONRICYT-eBooks. Download chapter PDF
Similar content being viewed by others
Keywords
1 Introduction
Consistent reconstruction is a method for estimating a signal \(x \in \mathbb{R}^{d}\) from a collection of linear measurements that have been corrupted by uniform noise or, more generally, bounded noise. Estimation with uniform noise arises naturally in quantization problems in signal processing, especially in connection with dithering and the uniform noise model [7, 11]. Consistent reconstruction has been used as a signal recovery method for memoryless scalar quantization [1, 2, 4, 11, 13], Sigma-Delta quantization [12], and compressed sensing [5, 6, 9]. See [10] for background and motivation on consistent reconstruction and estimation with uniform noise.
Let \(x \in \mathbb{R}^{d}\) be an unknown signal and let \(\{\varphi _{n}\}_{n=1}^{N} \subset \mathbb{R}^{d}\) be a given spanning set for \(\mathbb{R}^{d}\) that is used to make linear measurements 〈x, φ n 〉 of x. We consider the problem of recovering an estimate for x from the noisy measurements
where {ε n } n = 1 N are independent uniform random variables on [−δ, δ]. For the setting of this chapter, the collection {φ n } n = 1 N is known but randomly generated, the noise level δ > 0 is fixed and known, whereas x and the noise {ε n } n = 1 N are both unknown. We focus on the situation when {φ n } n = 1 N are independent versions of a random vector \(\varphi \in \mathbb{R}^{d}\) whose distribution we refer to as the sampling distribution.
Consistent reconstruction seeks an estimate \(\widetilde{x}\) for the unknown signal x that is consistent with the knowledge that the noise is bounded in [−δ, δ]. Specifically, consistent reconstruction produces an estimate \(\widetilde{x} \in \mathbb{R}^{d}\) for x by selecting any solution of the linear feasibility problem
There are generally infinitely many solutions to this feasibility problem. In this chapter, we mainly focus on the worst case error associated to consistent reconstruction.
1.1 Worst case error
To describe the worst case error of consistent reconstruction, note that if \(\widetilde{x}\) is any solution to (2), then the error \((\widetilde{x} - x)\) lies in each of the closed convex sets
The intersection of the sets E n forms the following error polytope:
which is the set of all possible errors associated to consistent reconstruction (2). The worst case error W N associated to consistent reconstruction is thus defined by
where ∥⋅ ∥ denotes the Euclidean norm on \(\mathbb{R}^{d}\).
1.2 Background
The main results in [10] proved error bounds for the expected worst case error squared \(\mathbb{E}[(W_{N})^{2}]\) of consistent reconstruction when the sampling vectors {φ n } n = 1 N are drawn at random from a suitable probability distribution on the unit sphere \(\mathbb{S}^{d-1}\).
The work in [10] considered sampling vectors \(\{\varphi _{n}\}_{n=1}^{N} \subset \mathbb{S}^{d-1}\) that are independently drawn instances of a unit-norm random vector φ that satisfies the following admissibility condition:
See Section 5 of [10] for further discussion of the admissibility condition (6). For example, if φ is uniformly distributed on \(\mathbb{S}^{d-1}\), then φ satisfies (6) with s = 1 and \(\alpha = \frac{2\varGamma (\frac{d} {2} )} {\sqrt{\pi }\varGamma (\frac{d-1} {2} )}\). On the other hand, if φ has a point mass, then φ does not satisfy (6).
Suppose that \(\{\varphi _{n}\}_{n=1}^{N} \subset \mathbb{S}^{d-1}\) are independently drawn at random according to a distribution that satisfies the admissibility condition (6). Theorem 5.5 and Corollary 5.6 in [10] prove that there exist absolute constants c 1, c 2 > 0 such that if
then the expected worst case error squared for consistent reconstruction satisfies
Moreover, in the special case when {φ N } n = 1 N are drawn independently at random according to the uniform distribution on \(\mathbb{S}^{d-1}\), Theorem 6.1 and Corollary 6.2 in [10] proved a refined error bound with a constant that has cubic dependence on the dimension
For perspective, it is known that mean squared error rates of order 1∕N 2 are generally optimal for estimation with uniform noise, see [11].
1.3 Overview and main results
The error bounds for consistent reconstruction in [10] only considered the mean squared error \(\mathbb{E}[(W_{N})^{2}]\) and only considered the admissibility condition (6) in the setting of unit-norm random vectors (for example, this excludes the case of Gaussian random vectors). The main contributions of this chapter are two-fold:
-
1.
We prove bounds on general error moments \(\mathbb{E}[(W_{N})^{p}]\) for consistent reconstruction. Our main results show that the error decreases like \(\mathbb{E}[(W_{N})^{p}]\lesssim 1/N^{p},\) as the number of measurements N increases.
-
2.
We establish a general admissibility condition on the sampling distribution that does not require φ to be unit-norm.
In Section 2, we prove our first main result, Theorem 1, which gives upper bounds on \(\mathbb{E}[(W_{N})^{p}]\) for unit-norm sampling distributions. Section 3 builds on Theorem 1 and proves our second main result, Theorem 2, for general sampling distributions that need not be unit-norm.
2 Error moments for consistent reconstruction: unit-norm distributions
In this section we prove our first main result, Theorem 1. Theorem 1 extends Theorem 5.5 in [10] to the setting of general error moments \(\mathbb{E}[(W_{N})^{p}]\). In this section, we assume that the sampling vectors {φ n } n = 1 N are unit-norm and satisfy the admissibility condition (6). We shall later remove the unit-norm requirement from the admissibility condition in Section 3.
2.1 Consistent reconstruction and coverage problems
We begin by recalling a useful connection between consistent reconstruction and a problem on covering the sphere by random sets.
Definition 1
Let \(\left \{\varphi _{n}\right \}_{n=1}^{N}\) be a set of unit-norm vectors and let {ε n } n = 1 N ⊂ [−δ, δ]. For each λ > 0, define
In our setting, the sets B n (λ) are random subsets of \(\mathbb{S}^{d-1}\) because {φ n } n = 1 N and {ε n } n = 1 N are random.
Note that each \(B_{n}\left (\lambda \right )\) can be expressed as a union of two (possibly empty) antipodal open spherical caps of different sizes
where the angular radii θ n + and θ n − are given by
and
The following lemma shows a connection between consistent reconstruction and the problem of covering the unit sphere by the random sets B n (λ), see Lemma 4.1 in [10].
Lemma 1
For all λ > 0, the worst case error satisfies
The following lemmas collect upper bounds on \(\,\text{Pr}\left [\mathbb{S}^{d-1}\not\subset \bigcup _{n=1}^{N}B_{n}\left (\lambda \right )\right ]\) that are spread out over various parts of [10].
Lemma 2
If λ ≥ 4δ, then
Lemma 2 was shown in equation (5.9) in [10].
Lemma 3
If 0 ≤ λ ≤ 4(2α)1∕s δ, then
where q(k, d − 1, α, s) satisfies
and
The bound (11) appears in (5.12) in [10]. The bound (12) follows from (5.11) in [10], and the bound (13) appears in Step VI in the proof of Theorem 5.5 in [10].
2.2 Error moment bounds
We now prove our first main result that provides error moment bounds for consistent reconstruction.
Theorem 1
Suppose that \(\{\varphi _{n}\}_{n=1}^{N} \subset \mathbb{S}^{d-1}\) are independently drawn at random according to a distribution that satisfies the admissibility condition (6) with parameters α ≥ 1 and 0 < s ≤ 1. If \(p \in \mathbb{N}\) and N ≥ (d + p)∕s, then the pth error moment for consistent reconstruction satisfies
where
and
Proof
We proceed by directly building on the proof of Theorem 5.5 in [10].
Step 1. We need to compute
By Lemma 1, we have
Thus, it suffices to bound the integral on right side of (16).
Step 2. We shall bound the integral in (16) by breaking it up into three separate integrals. We begin by estimating the integral in the range 0 ≤ λ ≤ 4δ(2α)1∕s.
Using (11) and a change of variables gives
Here, we used the property of the beta function that
It remains to bound the sum \(\sum _{k=0}^{N}\frac{(k+p-1)!} {k!} q(k,d - 1,\alpha,s)\) in (17). We will bound this sum by breaking it up into two separate sums, in an analogous manner to Step VI in the proof of Theorem 5.5 in [10]. Let
Since q(k, d − 1, α, s) ≤ 1, we have
Using (13) we have
where S p = ∑ k = 1 ∞(k + 1)p−1(3∕4)k∕2 satisfies 1 < S p < ∞.
Combining (17) and (22) yields
Step 3. Next, we bound the integral (16) in the range 4δ(2α)1∕s ≤ λ ≤ 8δ(2α)1∕s. By Lemma 2 we know that in this range of λ,
Thus
Step 4. We next bound the integral (16) in the range λ ≥ 8δ(2α)1∕s. By Lemma 2 we know that in this range of λ,
It follows that when N ≥ (d + p)∕s,
Combining (16), (23), (24), and (25) completes the proof.
Theorem 1 yields the following corollary.
Corollary 1
Suppose that \(\{\varphi _{n}\}_{n=1}^{N} \subset \mathbb{S}^{d-1}\) are independently drawn at random according to a distribution that satisfies the admissibility condition (6) with parameters α ≥ 1 and 0 < s ≤ 1. If \(p \in \mathbb{N}\) and
then
where C ′, C ″ are as in Theorem 1 .
Proof
In view of Theorem 1, it suffices to show that if N satisfies (26) then
Equivalently, it suffices to show
To begin, note that
gives
Next, use (29) and N ≥ (d + p)∕s ≥ max{p, 2} to obtain
In view of (30), to show (28) it suffices to have
Since (31) holds by the assumption (26), this completes the proof.
We conclude this section with some perspective on the dimension dependence of the constant C ′ in Theorem 1 and Corollary 1. We consider the special case when φ is uniformly distributed on the unit-sphere \(\mathbb{S}^{d-1}\) with d ≥ 3. In this case, one may take s = 1 and \(\alpha = \frac{2\varGamma (d/2)} {\sqrt{\pi }\varGamma ((d-1)/2)}\) in (6), see Example 5.1 in [10], and the constant C ′ is of order \(\left (d^{\frac{3} {2} }\ln d\right )^{p}\). Here, the logarithmic factor lnd is an artifact of the general setting of Theorem 1. In particular, for p = 2 the refined analysis in Theorem 6.1 and Corollary 6.2 of [10] shows that the factor lnd can be removed when φ is uniformly distributed on the unit-sphere \(\mathbb{S}^{d-1}\). A similar analysis extends to moments with general values of \(p \in \mathbb{N}\) and shows that the factor lnd can be replaced by an absolute constant that is independent of d.
3 Error moments for consistent reconstruction: general distributions
In Section 2 we proved bounds on the pth error moment for consistent reconstruction when the measurements are made using i.i.d. copies of a unit-norm random vector \(\varphi \in \mathbb{S}^{d-1}\). In this section, we relax the unit-norm constraint to accommodate more general distributions.
3.1 General admissibility condition
Definition 2
We shall say that a random vector \(\varphi \in \mathbb{R}^{d}\) satisfies the general admissibility condition if the following conditions hold:
-
φ = aψ, where a is a non-negative random variable, ψ is a unit-norm random vector, and a and ψ are independent.
-
ψ satisfies the admissibility condition (6).
-
\(\exists C> 0\) such that
$$\displaystyle{ \forall \lambda> 0,\ \ \ \lambda \Pr [a\lambda \leq 1] \leq C. }$$(32) -
\(r_{a} =\Pr [a> 1]\) satisfies 0 < r a < 1.
Example 1
A sufficient condition for the small-ball inequality (32) to hold is when a is an absolutely continuous random variable whose probability density function f is in \(L^{\infty }(\mathbb{R})\). In this case, for each λ > 0,
This shows that a large class of probability distributions satisfy the conditions in Definition 2. For example, if φ is a random vector whose entries are i.i.d zero mean Gaussian random variables, then φ satisfies the conditions in Definition 2.
In Definition 2, there would be no loss of generality if a were scaled differently so that \(0 <\Pr [a> T] <1\) for some T > 0. In particular, suppose that φ n = a n ψ n with \(0 <\Pr [a_{n}> T] <1\), and q n = 〈x, φ n 〉 + ε n with ε n uniformly distributed on [−δ, δ]. Then \(\widetilde{x} \in \mathbb{R}^{d}\) satisfies
where φ n ′ = φ n ∕T = a n ′ ψ n and a n ′ = a n ∕T and q n ′ = 〈x, φ n ′〉 + ε n ′, where ε n ′ = ε n ∕T is uniformly distributed on [−δ ′, δ ′] with δ ′ = δ∕T.
3.2 Coverage problems revisited
Suppose that {φ n } n = 1 N are i.i.d. versions of a random vector φ that satisfies the conditions of Definition 2. In particular, φ n = a n ψ n , where {a n } n = 1 N i.i.d. versions of a random variable a, and {ψ n } n = 1 N are i.i.d. versions of a random vector ψ. Similar to Lemma 1, the worst case error W N for consistent reconstruction can be bounded by
where B(ψ n , ε n , a n λ) is defined using (7).
3.2.1 Conditioning and a bound by caps with a n = 1
The following lemma bounds (33) by coverage probabilities involving caps with a n = 1.
Lemma 4
Suppose {φ n } n = 1 N , with φ n = a n ψ n , are i.i.d. versions of a random vector φ that satisfies the conditions of Definition 2 . Then
where
and \(r = r_{a} =\Pr [a> 1]\) is as in Definition 2 .
Proof
Let \(\mathscr{J}_{j,N}\) denote the event that exactly j elements of {a n } n = 1 N satisfy a n > 1. Since the {a n } n = 1 N are independent versions of the random variable a,
Thus,
By (7), when a n > 1 we have B(ψ n , ε n , a n λ) ⊃ B(ψ n , ε n , λ). Thus for 1 ≤ j ≤ N,
where the last equality holds because \(\left \{a_{n}\right \}_{n=1}^{N}\) are i.i.d. random variables that are independent of the i.i.d. random vectors {ψ n } n = 1 N. For j = 0, we use the trivial bound
Combining (35) and (36) completes the proof.
To bound the binomial terms in Lemma 4 it will be useful to recall Hoeffding’s inequality for Bernoulli random variables. If 0 < p < 1 and m ≤ Np, then
3.2.2 Covering and discretization
A useful technique for bounding coverage probabilities such as (33) is to discretize the problem by discretizing the sphere \(\mathbb{S}^{d-1}\) with an ε-net, see [3]. In this section, we briefly recall necessary aspects of this discretization method as used in [10].
Recall that a set \(\mathscr{N}_{\epsilon } \subset \mathbb{S}^{d-1}\) is a geodesic ε-net for \(\mathbb{S}^{d-1}\) if
For the remainder of this section, let \(\mathscr{N}_{\epsilon }\) be a geodesic ε- net of cardinality
It is well known that geodesic ε-nets of such cardinality exist, e.g., see Lemma 13.1.1 in [8] or Section 2.2 in [10].
Recall that a set \(\mathscr{N}_{\epsilon } \subset \mathbb{S}^{d-1}\) is a geodesic ε-net for \(\mathbb{S}^{d-1}\) if
For the remainder of this section, let \(\mathscr{N}_{\epsilon }\) be a geodesic ε- net of cardinality
It is well known that geodesic ε-nets of such cardinality exist, e.g., see Lemma 13.1.1 in [8] or Section 2.2 in [10].
Recalling (8), define the shrunken bi-cap \(T_{\epsilon }\left [B(\psi _{n},\epsilon _{n},a_{n}\lambda )\right ]\) by
where
Similar to equations (5.4) and (5.5) in [10], the coverage probability (33) can be discretized as follows:
Similar to equation (5.6) in [10], one has that
and
This gives
3.3 Moment bounds for general distributions
We now state our next main theorem.
Theorem 2
Suppose that \(\left \{\varphi _{n}\right \}_{n=1}^{N}\) are i.i.d. versions of a random vector φ that satisfies the conditions of Definition 2 . Let \(r = r_{a} =\Pr [a> 1]\) be as in Definition 2 . If
then the pth error moment for consistent reconstruction satisfies
where C ′, C ″ are as in Theorem 1 , Λ is defined by (42) and (57), and C ‴ is defined by (60) and (57).
Proof
As in Theorem 1 we shall use (15). In view of (33), we need to estimate
Step 1. We begin by estimating the integral in (41) over the range 0 ≤ λ ≤ Λδ, where
and K ″ is defined in (57).
By Lemma 4 we have
Hoeffding’s inequality and the trivial bound \(\Pr \left [\mathbb{S}^{d-1}\not\subset \bigcup _{n=1}^{j}B(\psi _{n},\epsilon _{n},\lambda )\right ] \leq 1\) can be used to bound (43) as follows:
To bound the integral in (44), recall (40) and note that if j satisfies (d + p)∕s ≤ ⌈Nr∕2⌉ ≤ j ≤ N, then the bounds on (16) obtained in the proof of Theorem 1 give that
where C ′ and C ″ are as in Theorem 1.
Using (46), along with ∑ j = 0 Nbino(j, N, r) = 1, one may bound (44) as follows:
Applying the bounds (45) and (47) to (43) and (44) gives
Step 2. We next estimate the integral in (41) over the range λ ≥ Λδ. By (38) and (39) we have
We therefore need to bound \(\Pr [\vert \langle z,\psi _{n}\rangle \vert \leq \frac{2\delta } {a_{n}\lambda }+\epsilon ]\).
For the remainder of this step set
where C, α, s are the parameters in (6) and Definition (2). By (42), note that λ ≥ Λδ ≥ Λ 0 δ implies that 0 < ε ≤ 1∕4.
For any \(z \in \mathbb{S}^{d-1}\) we have
We now bound the terms appearing in (51). Recall that λ ≥ Λδ implies that 4δ∕(Aλ) = 2ε ≤ 1∕2. By our choice of ε in (50), and using the admissibility assumption (6), for each λ ≥ Λδ one has
To bound (52), note that by (32) one has \(\,\text{Pr}\left [a_{n} \leq A\right ] \leq CA\), and thus
Using the bounds (53) and (54) in (51) and (52) gives
Since our choice of A in (50) gives
we have
Thus, combining (49) and (56) gives
To simplify notation, let
so that
Since 0 < s ≤ 1 and 0 < r < 1, note that (40) implies \(\left (\frac{sN-d+1} {s+1} - p + 1\right ) \geq 2\). By (58) we have
Since (42) implies that \(K^{{\prime\prime}}\left (\frac{4} {\varLambda } \right )^{ \frac{s} {s+1} } \leq 1/2\), it follows that
where
Combining (41), (48) and (59) completes the proof.
Similar to Corollary 1, the following corollary of Theorem 2 shows that \(\mathbb{E}[(W_{N})^{p}]\) is at most of order 1∕N p when N is sufficiently large.
Corollary 2
Let {φ n } n = 1 N be as in Theorem 2 . There exist constants C 1, C 2 > 0 such that
The constants C 1, C 2 depend on α, s, C, p, d.
3.4 Numerical experiment
This section illustrates Theorem 2 with a numerical experiment.
Let x = (2, π) and \(\delta = \frac{1} {10}\). Given N ≥ 3, let \(\{e_{n}\}_{n=1}^{N} \subset \mathbb{R}^{2}\) be independent random vectors with i.i.d. N(0, 1) entries. Let {q n } n = 1 N be defined as in (1). Since there infinitely many different solutions \(\widetilde{x}\) to the consistent reconstruction condition (2), we select the minimal norm estimate by
We repeat this experiment 20 times and let E(N, p) denote the average value of \(\|\widetilde{x} - x\|^{p}\). Figures 1 and 2 show log-log plots of E(N, p) versus N for p = 2 and p = 5. For comparison, these respective figures also show log-log plots of 3∕N 2 and 20∕N 5 versus N. In particular, E(N, p) appears to decay like 1∕N p, as predicted by the worst case error bounds in Theorem 2.
References
Z. Cvetković, Resilience properties of redundant expansions under additive noise and quantization. IEEE Trans. Inf. Theory 49, 644–656 (2003)
Z. Cvetković, M. Vetterli, On simple oversampled A/D conversion in \(L^{2}(\mathbb{R})\). IEEE Trans. Inf. Theory 47, 146–154 (2001)
N. Flatto, D.J. Newman, Random coverings. Acta Math. 128, 241–264 (1977)
V.K. Goyal, M. Vetterli, N.T. Thao, Quantized overcomplete expansions in \(\mathbb{R}^{n}\): analysis, synthesis, and algorithms. IEEE Trans. Inf. Theory 44, 16–30 (1998)
L. Jacques, D.K. Hammond, J.M. Fadili, Dequantizing compressed sensing: when oversampling and non-Gaussian constraints combine. IEEE Trans. Inf. Theory 57, 560–571 (2011)
L. Jacques, J.N. Laska, P.T. Boufounos, R.G. Baraniuk, Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors. IEEE Trans. Inf. Theory 59, 2082–2102 (2013)
D. Jimenez, L. Wang, Y. Wang, White noise hypothesis for uniform quantization errors. SIAM J. Math. Anal. 38, 2042–2056 (2007)
J. Matoušek, Lectures on Discrete Geometry (Springer, New York, 2002)
Y. Plan, R. Vershynin, One-bit compressed sensing by linear programming. Commun. Pure Appl. Math. 66, 1275–1297 (2013)
A.M. Powell, J.T. Whitehouse, Error bounds for consistent reconstruction: random polytopes and coverage processes. Found. Comput. Math. 16, 395–423 (2016)
S. Rangan, V.K. Goyal, Recursive consistent estimation with bounded noise. IEEE Trans. Inf. Theory 47, 457–464 (2001)
N.T. Thao, M. Vetterli, Deterministic analysis of oversampled A/D conversion and decoding improvement based on consistent estimates. IEEE Trans. Signal Process. 42, 519–531 (1994)
N.T. Thao, M. Vetterli, Reduction of the MSE in R-times oversampled A/D conversion from \(\mathscr{O}(R^{-1})\) to \(\mathscr{O}(R^{-2})\). IEEE Trans. Signal Process. 42, 200–203 (1994)
Acknowledgements
C.-H. Lee was partially supported by NSF DMS 1211687. A.M. Powell was partially supported by NSF DMS 1521749 and NSF DMS 1211687. A.M. Powell gratefully acknowledges the hospitality and support of the Academia Sinica Institute of Mathematics (Taipei, Taiwan).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this chapter
Cite this chapter
Lee, CH., Powell, A.M., Whitehouse, J.T. (2017). Consistent Reconstruction: Error Moments and Sampling Distributions. In: Balan, R., Benedetto, J., Czaja, W., Dellatorre, M., Okoudjou, K. (eds) Excursions in Harmonic Analysis, Volume 5. Applied and Numerical Harmonic Analysis. Birkhäuser, Cham. https://doi.org/10.1007/978-3-319-54711-4_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-54711-4_9
Published:
Publisher Name: Birkhäuser, Cham
Print ISBN: 978-3-319-54710-7
Online ISBN: 978-3-319-54711-4
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)