On subspaces spanned by random selections of ±1 vectors

Research output: Contribution to journalArticle

26 Citations (Scopus)

Abstract

Let vectors v1, ..., vp be chosen at random from the ±1 vectors of length n. The probability that there is at least one ±1 vector in the subspace (over the reals) spanned by v1, ..., vp that is different from the ±vj is shown to be 4 p 3 3 4n +O 7 10n, as n → ∞, for p ≤ n - 10n (log n), where the constant implied by the O-notation is independent of p. The main term in this estimate is the probability that some three of the vj contain another ±1 vector in their linear span. This result answers a question that arose in the work of Kanter and Sompolinsky on associative memories.

Original languageEnglish (US)
Pages (from-to)124-133
Number of pages10
JournalJournal of Combinatorial Theory, Series A
Volume47
Issue number1
DOIs
StatePublished - Jan 1 1988
Externally publishedYes

Fingerprint

Subspace
Associative Memory
Notation
Data storage equipment
Term
Estimate

Cite this

On subspaces spanned by random selections of ±1 vectors. / Odlyzko, Andrew.

In: Journal of Combinatorial Theory, Series A, Vol. 47, No. 1, 01.01.1988, p. 124-133.

Research output: Contribution to journalArticle

@article{4f1179f612344e6fad34752ef58c6fa2,
title = "On subspaces spanned by random selections of ±1 vectors",
abstract = "Let vectors v1, ..., vp be chosen at random from the ±1 vectors of length n. The probability that there is at least one ±1 vector in the subspace (over the reals) spanned by v1, ..., vp that is different from the ±vj is shown to be 4 p 3 3 4n +O 7 10n, as n → ∞, for p ≤ n - 10n (log n), where the constant implied by the O-notation is independent of p. The main term in this estimate is the probability that some three of the vj contain another ±1 vector in their linear span. This result answers a question that arose in the work of Kanter and Sompolinsky on associative memories.",
author = "Andrew Odlyzko",
year = "1988",
month = "1",
day = "1",
doi = "10.1016/0097-3165(88)90046-5",
language = "English (US)",
volume = "47",
pages = "124--133",
journal = "Journal of Combinatorial Theory - Series A",
issn = "0097-3165",
publisher = "Academic Press Inc.",
number = "1",

}

TY - JOUR

T1 - On subspaces spanned by random selections of ±1 vectors

AU - Odlyzko, Andrew

PY - 1988/1/1

Y1 - 1988/1/1

N2 - Let vectors v1, ..., vp be chosen at random from the ±1 vectors of length n. The probability that there is at least one ±1 vector in the subspace (over the reals) spanned by v1, ..., vp that is different from the ±vj is shown to be 4 p 3 3 4n +O 7 10n, as n → ∞, for p ≤ n - 10n (log n), where the constant implied by the O-notation is independent of p. The main term in this estimate is the probability that some three of the vj contain another ±1 vector in their linear span. This result answers a question that arose in the work of Kanter and Sompolinsky on associative memories.

AB - Let vectors v1, ..., vp be chosen at random from the ±1 vectors of length n. The probability that there is at least one ±1 vector in the subspace (over the reals) spanned by v1, ..., vp that is different from the ±vj is shown to be 4 p 3 3 4n +O 7 10n, as n → ∞, for p ≤ n - 10n (log n), where the constant implied by the O-notation is independent of p. The main term in this estimate is the probability that some three of the vj contain another ±1 vector in their linear span. This result answers a question that arose in the work of Kanter and Sompolinsky on associative memories.

UR - http://www.scopus.com/inward/record.url?scp=38249029967&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249029967&partnerID=8YFLogxK

U2 - 10.1016/0097-3165(88)90046-5

DO - 10.1016/0097-3165(88)90046-5

M3 - Article

VL - 47

SP - 124

EP - 133

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

SN - 0097-3165

IS - 1

ER -