Journal article

On the construction of sparse matrices from expander graphs

Abstract:

We revisit the asymptotic analysis of probabilistic construction of adjacency matrices of expander graphs proposed in Bah and Tanner [1]. With better bounds we derived a new reduced sample complexity for d, the number of non-zeros per column of these matrices (or equivalently the left-degree of the underlying expander graph). Precisely d=O(logs(N/s)); as opposed to the standard d=O(log(N/s)), where N is the number of columns of the matrix (also the cardinality of set of left vertices of the e...

Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Access Document

Files:
• (pdf, 931.7KB)
Publisher copy:
10.3389/fams.2018.00039

Authors

More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Mathematical Institute
Oxford college:
Exeter College
Role:
Author
More from this funder
Funding agency for:
Tanner, J
Publisher:
Frontiers Media Publisher's website
Journal:
Frontiers in Applied Mathematics and Statistics Journal website
Volume:
4
Pages:
Article: 39
Publication date:
2018-09-04
Acceptance date:
2018-08-10
DOI:
ISSN:
2297-4687
Pubs id:
pubs:911758
URN:
uri:29281a91-f740-41a2-a129-05e6e8377b53
UUID:
uuid:29281a91-f740-41a2-a129-05e6e8377b53
Local pid:
pubs:911758
Keywords: