Numerical algorithms for the mathematics of information

Mendoza-Smith, R

Abstract:: This thesis presents a series of algorithmic innovations in Combinatorial Compressed Sensing and Persistent Homology. The unifying strategy across these contributions is in translating structural patterns in the underlying data into specific algorithmic designs in order to achieve: better guarantees in computational complexity, the ability to operate on more complex data, highly efficient parallelisations, or any combination of these.

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Share
Cite

Cite this record

APA Style

Mendoza-Smith, R. (2017). Numerical algorithms for the mathematics of information [PhD thesis]. University of Oxford.

MLA Style

Mendoza-Smith, R. Numerical Algorithms for the Mathematics of Information. 2017. University of Oxford, PhD thesis.

Chicago Style

Mendoza-Smith, R. 2017. “Numerical Algorithms for the Mathematics of Information.” PhD thesis, University of Oxford.
Print

Access Document

Files:: thesis_ora.pdf

(Preview, pdf, 9.4MB, Terms of use)

Authors

+ Mendoza-Smith, R More by this author

Division:: MPLS
Department:: Mathematical Institute
Department:: University of Oxford
Role:: Author

Contributors

+ Tanner, J

Department:: University of Oxford
Role:: Supervisor

+ Nanda, V

Department:: University of Oxford
Role:: Examiner

+ Calderbank, R

Department:: Duke University
Role:: Examiner

+ Consejo Nacional de Ciencia y Tecnologia (Mexico) More from this funder

Funding agency for:: Mendoza-Smith, R

DOI:: 10.5287/ora-pm9p4pmjj
Type of award:: DPhil
Level of award:: Doctoral
Awarding institution:: University of Oxford

Language:: English
Keywords:: Parallel Algorithms

Persistent Homology

Computational Algebraic Topology

Compressed sensing

Combinatorial compressed sensing

Topological Data Analysis

Numerical Analysis

Expander graphs
Subjects:: Persistent Homology

Numerical Analysis

Compressed sensing (Telecommunication)

Topological Data Analysis

Computational Algebraic Topology
UUID:: uuid:451a418b-eca0-454f-8b54-7b6476056969
Deposit date:: 2018-10-11
ARK identifier:: ark:/29072/ora_451a418beca0454f8b547b6476056969

Related item:: Expander L0-decoding
Description:: We introduce two new algorithms, Serial-L0 and Parallel-L0 for solving a large underdetermined linear system of equations $y=Ax \in R^m$ when it is known that $x\in R^n$ has at most $k
Related item:: A Robust Parallel Algorithm for Combinatorial Compressed Sensing
Description:: It was shown in previous work that a vector $x \inR^n$ with at most $k < n$ nonzeros can be recovered from an expander sketch $Ax$ in $O(nnz(A) log k)$ operations via the parallel-L0 decoding algorithm, where $nnz(A)$ denotes the number of nonzero entries in $A \in R^{m \ imes n}$ . In this paper, we present the robust-L0 decoding algorithm, which robustifies parallel-L0 when the sketch $Ax$ is corrupted by additive noise. This robustness is achieved by approximating the asymptotic posterior distribution of values in the sketch given its corrupted measurements. We provide analytic expressions that approximate these posteriors under the assumptions that the nonzero entries in the signal and the noise are drawn from continuous distributions. Numerical experiments presented show that robust-L0 is superior to existing greedy and combinatorial compressed sensing algorithms in the presence of small to moderate signal-to-noise ratios in the setting of Gaussian signals and Gaussian additive noise.
Related item:: Parallel multi-scale reduction of persistent homology filtrations
Description:: The persistent homology pipeline includes the reduction of a, so-called, boundary matrix. We extend the work of Bauer et al. (2014) and Chen et al. (2011) where they show how to use dependencies in the boundary matrix to adapt the reduction algorithm presented in Edelsbrunner et al. (2002) in such a way as to reduce its computational cost. Herein we present a number of additional dependencies in the boundary matrices and propose a novel parallel algorithms for the reduction of boundary matrices. In particular, we show: that part of the reduction is immediately apparent, give bounds on the reduction needed for remaining columns, and from these give a framework for which the boundary reduction process can be massively parallelised. Simulations on four synthetic examples show that the computational burden can be conducted in approximately a thousandth the number of iterations needed by traditional methods. Moreover, whereas the traditional boundary reductions reveal barcodes sequentially from a filtration order, this approach gives an alternative method by which barcodes are partly revealed for multiple scales simultaneously and further refined as the algorithm progresses; simulations show that for a Vietoris-Rips filtration with $\sim10^4$ simplices, an estimate of the essential simplices with 95% precision can be computed in two iterations and that the reduction completed to within 1% in about ten iterations of our algorithm as opposed to nearly approximately eight thousand iterations for traditional methods.

Terms of use

Copyright holder:: Mendoza-Smith, R

Licence:: Terms and Conditions of Use for Oxford University Research Archive

Views and Downloads

About views and downloads

If you are the owner of this record, you can report an update to it here: Report update to this record

Thesis

Numerical algorithms for the mathematics of information

Actions

Access Document

Authors

Contributors

Terms of use

Views and Downloads

Altmetrics

Dimensions

Thesis

Numerical algorithms for the mathematics of information

Actions

Access Document

Authors

Contributors

Funding

Bibliographic Details

Item Description

Related Items

Terms of use

Metrics

Views and Downloads

Altmetrics

Dimensions