Date of Award
12-2014
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Legacy Department
Mathematical Science
Committee Chair/Advisor
Gao, Shuhong
Committee Member
Khan , Taufiquar
Committee Member
Dimitrova , Elena
Committee Member
Gao , Bruce
Abstract
Many computational problems are related to the model y = Ax + e, including compressive sensing, coding theory, dimensionality reduction, etc. The related algorithms are extremely useful in practical applications for high performance computing, for example, digital communications, biological imaging and data streaming, etc. This thesis studies two important problems. One problem is related to efficient decoding for Reed-Solomon codes over complex numbers. In this case, A and y are given, and the goal is to find an efficient stable algorithm to compute x. This is related to magnetic resonance imaging (MRI). The other problem is related to fast algorithms for projecting vectors in high dimensional spaces into low dimensional spaces so that their pairwise distances are nearly preserved. In this case, x is given (in a high dimensional space) and one needs to find a matrix A with some nice properties. This is called Johnson-Lindenstrauss transforms. On decoding Reed-Solomon (RS) codes, the thesis first briefly describes the current al- gorithms for decoding RS codes over finite fields, including the Sudan-Guruswami list decoding. However, almost all existing decoding algorithms for finite fields are not applicable over complex numbers since they are not numerically stable. The thesis proposes a new numerical algorithm based on Gao's gcd decoding algorithm. The algorithm can successfully correct burst errors over complex numbers. On Johnson-Lindenstrauss (JL) transforms, Kane and Nelson recently gave a sparse con- struction based on linear codes. The thesis shows how to use explicit codes to perform Kane and Nelson's fast JL transforms. The thesis also improves Kane and Nelson's bound for projections in dimensions that are useful in practice.
Recommended Citation
Mao, Yue, "Numerical decoding, Johnson-Lindenstrauss transforms, and linear codes" (2014). All Dissertations. 1420.
https://tigerprints.clemson.edu/all_dissertations/1420