On the construction of sparse matrices from expander graphs
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...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Frontiers Media
2018
|
| _version_ | 1797059614617894912 |
|---|---|
| author | Bah, B Tanner, J |
| author_facet | Bah, B Tanner, J |
| author_sort | Bah, B |
| collection | OXFORD |
| description | 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 expander graph) or the ambient dimension of the signals that can be sensed by such matrices. This gives insights into why using such sensing matrices with small d performed well in numerical compressed sensing experiments. Furthermore, we derive quantitative sampling theorems for our constructions which show our construction outperforming the existing state-of-the-art. We also used our results to compare performance of sparse recovery algorithms where these matrices are used for linear sketching. |
| first_indexed | 2024-03-06T20:06:47Z |
| format | Journal article |
| id | oxford-uuid:29281a91-f740-41a2-a129-05e6e8377b53 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:06:47Z |
| publishDate | 2018 |
| publisher | Frontiers Media |
| record_format | dspace |
| spelling | oxford-uuid:29281a91-f740-41a2-a129-05e6e8377b532022-03-26T12:17:29ZOn the construction of sparse matrices from expander graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:29281a91-f740-41a2-a129-05e6e8377b53Symplectic Elements at OxfordFrontiers Media2018Bah, BTanner, JWe 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 expander graph) or the ambient dimension of the signals that can be sensed by such matrices. This gives insights into why using such sensing matrices with small d performed well in numerical compressed sensing experiments. Furthermore, we derive quantitative sampling theorems for our constructions which show our construction outperforming the existing state-of-the-art. We also used our results to compare performance of sparse recovery algorithms where these matrices are used for linear sketching. |
| spellingShingle | Bah, B Tanner, J On the construction of sparse matrices from expander graphs |
| title | On the construction of sparse matrices from expander graphs |
| title_full | On the construction of sparse matrices from expander graphs |
| title_fullStr | On the construction of sparse matrices from expander graphs |
| title_full_unstemmed | On the construction of sparse matrices from expander graphs |
| title_short | On the construction of sparse matrices from expander graphs |
| title_sort | on the construction of sparse matrices from expander graphs |
| work_keys_str_mv | AT bahb ontheconstructionofsparsematricesfromexpandergraphs AT tannerj ontheconstructionofsparsematricesfromexpandergraphs |