Date of Award


Document Type


Degree Name

Doctor of Philosophy (PhD)

Legacy Department

Mathematical Science


Gao, Shuhong

Committee Member

Khan , Taufiquar

Committee Member

Dimitrova , Elena

Committee Member

Gao , Bruce


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.