Paper Info
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 4p334n +O 710n, 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.
Year
DOI
Venue
1988
10.1016/0097-3165(88)90046-5
Journal of Combinatorial Theory, Series A
DocType
Volume
Issue
Journal
47
1
ISSN
Citations 
PageRank 
0097-3165
2
0.54
References 
Authors
0
1
Name
Order
Citations
PageRank
Andrew M. Odlyzko11286413.71