Johnson-Lindenstrauss Lemma for Circulant Matrices

被引：37

作者：

Hinrichs, Aicke ^{[2
]}

Vybiral, Jan ^{[1
]}

机构：

[1] Austrian Acad Sci, Radon Inst Computat & Appl Math RICAM, A-4040 Linz, Austria

[2] Univ Jena, Dept Math, D-07740 Jena, Germany

来源：

RANDOM STRUCTURES & ALGORITHMS | 2011年 / 39卷 / 03期

关键词：

Johnson-Lindenstrauss lemma; circulant matrices; decoupling lemma;

D O I：

10.1002/rsa.20360

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We prove a variant of a Johnson-Lindenstrauss lemma for matrices with circulant structure. This approach allows to minimize the randomness used, is easy to implement and provides good running times. The price to be paid is the higher dimension of the target space k = O(epsilon(-2) log(3) n) instead of the classical bound k = O(epsilon(-2) log n). (C) 2011 Wiley Periodicals, Inc. Random Struct. Alg., 39, 391-398, 2011

引用

页码：391 / 398

页数：8

共 18 条

[1] Database-friendly random projections: Johnson-Lindenstrauss with binary coins [J].

Achlioptas, D .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 66 (04) :671-687

[2]

AILON N, ALMOST OPTIMAL UNRES

[3] THE FAST JOHNSON-LINDENSTRAUSS TRANSFORM AND APPROXIMATE NEAREST NEIGHBORS [J].

Ailon, Nir ;

Chazelle, Bernard .

SIAM JOURNAL ON COMPUTING, 2009, 39 (01) :302-322

[4]

[Anonymous], 2009, P SPARS 09 SIGN PROC

[5]

[Anonymous], STUDIA MATH

[6]

BAJWA W, 2007, IEEE WORKSH SSP MAD

[7]

BAJWA WU, 2008, P CISS08 PRINC

[8] INVERTIBILITY OF LARGE SUBMATRICES WITH APPLICATIONS TO THE GEOMETRY OF BANACH-SPACES AND HARMONIC-ANALYSIS [J].

BOURGAIN, J ;

TZAFRIRI, L .

ISRAEL JOURNAL OF MATHEMATICS, 1987, 57 (02) :137-224

[9]

Chazelle B, 2006, P 38 ANN ACM S THEOR

[10] An elementary proof of a theorem of Johnson and Lindenstrauss [J].

Dasgupta, S ;

Gupta, A .

RANDOM STRUCTURES & ALGORITHMS, 2003, 22 (01) :60-65

← 1 2 →