Premium
On series of signed vectors and their rearrangements
Author(s) -
Banaszczyk Wojciech
Publication year - 2012
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20373
Subject(s) - permutation (music) , series (stratigraphy) , mathematics , combinatorics , struct , constant (computer programming) , sequence (biology) , random permutation , random sequence , discrete mathematics , physics , mathematical analysis , computer science , symmetric group , chemistry , biology , paleontology , biochemistry , distribution (mathematics) , acoustics , programming language
Let x 1 ,…, x m ∈ \input amssym $ \Bbb R$ n be a sequence of vectors with ∥ x i ∥ 2 ≤ 1 for all i . It is proved that there are signs ε 1 ,…,ε m = ±1 such that\documentclass{article} \usepackage{mathrsfs,amsmath, amssymb} \pagestyle{empty} \begin{document}\begin{align*} \|{\varepsilon}_1x_1+\cdots+{\varepsilon}_kx_k\|_2\le C_1\sqrt{n}+C_2\sqrt{\mathstrut\log m}, \qquad k=1,\ldots,m, \end{align*} \end{document} where C 1 , C 2 are some numerical constants. It is also proved that there are signs ε 1 ′ ,…,ε m ′= ±1 and a permutation π of {1,…, m } such that\documentclass{article} \usepackage{mathrsfs,amsmath, amssymb} \pagestyle{empty} \begin{document}\begin{align*} \big\|{\varepsilon}_1^\prime x_{\pi(1)}+\cdots+{\varepsilon}_k^{\prime}x_{\pi(k)}\big\|_2\le C^{\prime}\sqrt n,\qquad k=1,\ldots,m, \end{align*} \end{document} where C ′ is some other numerical constant. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011