<Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>-Quantization and clustering in Banach spaces

LetX be a random variable with distribution μ taking values in a Banach spaceH. First, we establish the existence of an optimal quantization of μ with respect to the L ₁-distance. Second, we propose several estimators of the optimal quantizer in the potentially infinite-dimensional space H, with associated algorithms. Finally, we discuss practical results obtained from real-life data sets.     

Some remarks on the existence of optimal quantizers

Necessary and sufficient conditions are given for the existence of optimal k-dimensional quantizers that minimize a distortion measure E{W(X)C(X ? Q(X))}. An example is given in which a globally optimal quantizer does not exist.     

Optimal vector quantization in terms of Wasserstein distance

The optimal quantizer in memory-size constrained vector quantization induces a quantization error which is equal to a Wasserstein distortion. However, for the optimal (Shannon-)entropy constrained quantization error a proof for a similar identity is still missing. Relying on principal results of the optimal mass transportation theory, we will prove that the optimal quantization error is equal to a Wasserstein distance. Since we will state the quantization problem in a very general setting, our approach includes the Rényi-α-entropy as a complexity constraint, which includes the special case of (Shannon-)entropy constrained (α=1) and memory-size constrained (α=0) quantization. Additionally, we will derive for certain distance functions codecell convexity for quantizers with a finite codebook. Using other methods, this regularity in codecell geometry has already been proved earlier by György and Linder (2002, 2003) [11] and [12].     

A Local Refinement Strategy for Constructive Quantization of Scalar SDEs

We present a fully constructive method for quantization of the solution X of a scalar SDE in the path space L _p [0,1] or C[0,1]. The construction relies on a refinement strategy which takes into account the local regularity of X and uses Brownian motion (bridge) quantization as a building block. Our algorithm is easy to implement, its computational cost is close to the size of the quantization, and it achieves strong asymptotic optimality provided this property holds for the Brownian motion (bridge) quantization.     

An optimal Berry-Esseen type inequality for expectations of smooth functions

We provide an optimal Berry-Esseen type inequality for Zolotarev’s ideal ζ₃-metric measuring the difference between expectations of sufficiently smooth functions, like |·|³, of a sum of independent random variables X ₁,..., X _n with finite third-order moments and a sum of independent symmetric two-point random variables, isoscedastic to the X _i . In the homoscedastic case of equal variances, and in particular, in case of identically distributed X ₁,..., X _n the approximating law is a standardized symmetric binomial one. As a corollary, we improve an already optimal estimate of the accuracy of the normal approximation due to Tyurin (2009).     

Deformation quantization in algebraic geometry

We study deformation quantizations of the structure sheaf O_X of a smooth algebraic variety X in characteristic 0. Our main result is that when X is D-affine, any formal Poisson structure on X determines a deformation quantization of O_X (canonically, up to gauge equivalence). This is an algebro-geometric analogue of Kontsevich's celebrated result.     

Optimal solution of a Monge-Kantorovitch transportation problem

Suppose that P and Q are probabilities on a separable Banach space $\text{E}$. It is known that if (P, Q) satisfies certain regularity conditions and a random variable X has law P, then there exists a function $\text{f :}\text{E}\text{→}\text{E}$, such that the function f(X) has the law Q and the random pair (X, f(X)) is an optimal coupling for the Monge-Kantorovitch problem. In this paper we provide an approximation of the function f when the law Q is discrete. Thenwe extend this main result to any law Q. The proofs are based on a relationship between optimal couplings and nonlinear equations.     

Lattice quantization error for redundant representations

Redundant systems such as frames are often used to represent a signal for error correction, denoising and general robustness. In the digital domain quantization needs to be performed. Given the redundancy, the distribution of quantization errors can be rather complex. In this paper we study quantization error for a signal X in represented by a frame using a lattice quantizer. We completely characterize the asymptotic distribution of the quantization error as the cell size of the lattice goes to zero. We apply these results to get the necessary and sufficient conditions for the asymptotic form of the White Noise Hypothesis in the case of the pulse-code modulation scheme.     

The β α-Encoders for Robust A/D Conversion

The β-encoder, introduced as an alternative to binary encoding in A/D conversion, creates a quantization scheme robust with respect to quantizer imperfections by the use of a β-expansion, where 1<β<2. In this paper we introduce a more general encoder called the β α-encoder, that can offer more flexibility in design and robustness without any significant drawback on the exponential rate of convergence of the obtained expansion. Mathematically, the β α-encoder gives rise to a dynamical system that is both very interesting and challenging.     

Error bounds for high-resolution quantization with Rényi-α-entropy constraints

We consider the problem of optimal quantization with norm exponent r > 0 for Borel probability measures on ? ^d under constrained Rényi-α-entropy of the quantizers. If the bound on the entropy becomes large, then sharp asymptotics for the optimal quantization error are well-known in the special cases α = 0 (memory-constrained quantization) and α = 1 (Shannon-entropy-constrained quantization). In this paper we determine sharp asymptotics for the optimal quantization error under large entropy bound with entropy parameter α ∈ [1+r/d,∞]. For α ∈ [0,1 + r/d] we specify the asymptotical order of the optimal quantization error under large entropy bound. The optimal quantization error is decreasing exponentially fast with the entropy bound and the exact rate is determined for all α ∈ [0, ∞].     

A periodic-review inventory system with a capacitated backup supplier for mitigating supply disruptions

We consider a periodic-review inventory system with two suppliers: an unreliable regular supplier that may be disrupted for a random duration, and a reliable backup supplier that can be used during a disruption. The backup supplier charges higher unit purchasing cost and fixed order cost when compared to the regular supplier. Because the backup supplier is used at unplanned moments, its capacity to replenish inventory is considered limited. Analytical results partially characterize the structure of the optimal order policy: a state-dependent (X(i), Y(i)) band structure (with corresponding bounds of X(i) and Y(i) to be given), where i represents the status of the regular supplier. Numerical studies illustrate the structure of the optimal policy and investigate the impacts of major parameters on optimal order decisions and system costs.     

Asymptotic Optimality of Scalar Gersho Quantizers

In his famous paper (Gersho, IEEE Trans. Inf. Theory 25(4):373–380, 1979), Gersho stressed that the codecells of optimal quantizers asymptotically make an equal contribution to the distortion of the quantizer. Motivated by this fact, we investigate in this paper quantizers in the scalar case, where each codecell contributes with exactly the same portion to the quantization error. We show that such quantizers of Gersho type—or Gersho quantizers for short—exist for nonatomic scalar distributions. As a main result, we prove that Gersho quantizers are asymptotically optimal.     

The Littlewood-Offord problem and invertibility of random matrices

We prove two basic conjectures on the distribution of the smallest singular value of random n×n matrices with independent entries. Under minimal moment assumptions, we show that the smallest singular value is of order n−1/2, which is optimal for Gaussian matrices. Moreover, we give a optimal estimate on the tail probability. This comes as a consequence of a new and essentially sharp estimate in the Littlewood-Offord problem: for i.i.d. random variables Xk and real numbers ak, determine the probability p that the sum k_∑akXk lies near some number v. For arbitrary coefficients ak of the same order of magnitude, we show that they essentially lie in an arithmetic progression of length 1/p.     

Least squares cross-validation for the kernel deconvolution density estimatorValidation croisée pour l'estimateur à noyau de la déconvolution d'une densité

Assume we have i.i.d. replications from the corrupted random variable Y=X+ε, where X and ε are independent. We propose a data-driven bandwidth based on cross-validation ideas, for the kernel deconvolution estimator of the density of X. The proposed method is shown to be asymptotically optimal. To cite this article: É. Youndjé, M.T. Wells, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 509–513.     

Non-linear regression in credibility theory

Let X be a random vector with distribution depending on a parameter treated as a random variable ?. The usual linear regression assumption is that E(X|?) can be displayed in the form yβ(?) where y is a fixed design matrix and β(?) an unknown vector. In the present paper we assume that E(X|?) is a rather arbitrary function ?(β(?)) of the unknown vector β(?) and we derive credibility approximations for β(?).     

Limiting behavior of a diffusion in an asymptotically stable environment

Let V be a two sided random walk and let X denote a real valued diffusion process with generator . This process is the continuous equivalent of the one-dimensional random walk in random environment with potential V. Hu and Shi (1997) described the Lévy classes of X in the case where V behaves approximately like a Brownian motion. In this paper, based on some fine results on the fluctuations of random walks and stable processes, we obtain an accurate image of the almost sure limiting behavior of X when V behaves asymptotically like a stable process. These results also apply for the corresponding random walk in random environment.     

On a continuous analogue of the stochastic difference equation Xn=ρXn-1+Bn

Let B₁, B₂, ... be a sequence of independent, identically distributed random variables, letX₀ be a random variable that is independent ofB_n forn?1, let ρ be a constant such that 0<ρ<1 and letX₁,X₂, ... be another sequence of random variables that are defined recursively by the relationshipsX_n=ρX_n-1+B_n. It can be shown that the sequence of random variablesX₁,X₂, ... converges in law to a random variableX if and only ifE[log⁺¦B₁¦]<∞. In this paper we let {B(t):0≦t<∞} be a stochastic process with independent, homogeneous increments and define another stochastic process {X(t):0?t<∞} that stands in the same relationship to the stochastic process {B(t):0?t<∞} as the sequence of random variablesX₁,X₂,...stands toB₁,B₂,.... It is shown thatX(t) converges in law to a random variableX ast →+∞ if and only ifE[log⁺¦B(1)¦]<∞ in which caseX has a distribution function of class L. Several other related results are obtained. The main analytical tool used to obtain these results is a theorem of Lukacs concerning characteristic functions of certain stochastic integrals.     

Deterministic sampling of sparse trigonometric polynomials

One can recover sparse multivariate trigonometric polynomials from a few randomly taken samples with high probability (as shown by Kunis and Rauhut). We give a deterministic sampling of multivariate trigonometric polynomials inspired by Weil’s exponential sum. Our sampling can produce a deterministic matrix satisfying the statistical restricted isometry property, and also nearly optimal Grassmannian frames. We show that one can exactly reconstruct every M-sparse multivariate trigonometric polynomial with fixed degree and of length D from the determinant sampling X, using the orthogonal matching pursuit, and with |X| a prime number greater than (MlogD)². This result is optimal within the (logD)² factor. The simulations show that the deterministic sampling can offer reconstruction performance similar to the random sampling.     

Estimation de la transition de probabilité d'une chaîne de Markov doëblin-récurrente. étude du cas du processus autorégressif général d'ordre 1

We consider an homogenous Markov chain {X_n}. We estimate its transition probability density with kernel estimators. We apply these methods to the estimation of the unknown function f of the process defined by X₁ and X_n+1 = f(X_n) + ε_n, where {ε_n} is a noise (sequence of independent identically distributed random variables) of unknown law. The mean quadratic integrated rates of convergence are identical to those of classical density estimations. These risks are used here because we want some global informations about our estimates. We also study the average of those risks when the variance changes; it is shown that they reach a minimal value for some optimal variance. We study uniform convergence of our estimators. We finally estimate the variance of the noise and its density.     

L 1 bounds for asymptotic normality of random sums of independent random variables

We present upper bounds of L ₁ norms in the central limit theorem for random sums of independent random variables X ₁ , X ₂ , . . . , where the number of summands N is a nonnegative integer-valued random variable, independent of the summands X ₁ , X ₂ , . . . .