New directions in sparse sampling and estimation for underdetermined systems

A central objective in signal processing is to infer meaningful information from a set of measurements or data. While most signal models have an overdetermined structure (the number of unknowns less than the number of equations), traditionally very few statistical estimation problems have considered a data model which is underdetermined (number of unknowns more than the number of equations). However, in recent times, an explosion of theoretical and computational methods have been developed primarily to study underdetermined systems by imposing sparsity on the unknown variables. This is motivated by the observation that inspite of the huge volume of data that arises in sensor networks, genomics, imaging, particle physics, web search etc., their information content is often much smaller compared to the number of raw measurements. This has given rise to the possibility of reducing the number of measurements by down sampling the data, which automatically gives rise to underdetermined systems.

In this thesis, we provide new directions for estimation in an underdetermined system, both for a class of parameter estimation problems and also for the problem of sparse recovery in compressive sensing. There are two main contributions of the thesis: design of new sampling and statistical estimation algorithms for array processing, and development of improved guarantees for sparse reconstruction by introducing a statistical framework to the recovery problem.

We consider underdetermined observation models in array processing where the number of unknown sources simultaneously received by the array can be considerably larger than the number of physical sensors. We study new sparse spatial sampling schemes (array geometries) as well as propose new recovery algorithms that can exploit priors on the unknown signals and unambiguously identify all the sources. The proposed sampling structure is generic enough to be extended to multiple dimensions as well as to exploit different kinds of priors in the model such as correlation, higher order moments, etc.

Recognizing the role of correlation priors and suitable sampling schemes for underdetermined estimation in array processing, we introduce a correlation aware framework for recovering sparse support in compressive sensing. We show that it is possible to strictly increase the size of the recoverable sparse support using this framework provided the measurement matrix is suitably designed. The proposed nested and coprime arrays are shown to be appropriate candidates in this regard. We also provide new guarantees for convex and greedy formulations of the support recovery problem and demonstrate that it is possible to strictly improve upon existing guarantees.

This new paradigm of underdetermined estimation that explicitly establishes the fundamental interplay between sampling, statistical priors and the underlying sparsity, leads to exciting future research directions in a variety of application areas, and also gives rise to new questions that can lead to stand-alone theoretical results in their own right.

Multiplexed DNA-mediated electrochemistry

The aromatic core of double helical DNA possesses the unique and remarkable ability to form a conduit for electrons to travel over exceptionally long molecular distances. This core of π-stacked nucleobases creates an efficient pathway for charge transfer to proceed that is exquisitely sensitive to even subtle perturbations. Ground state electrochemistry of DNA-modified electrodes has been one of the major techniques used both to investigate and to harness the property of DNA-mediated charge transfer. DNA-modified electrodes have been an essential tool for both gaining insights into the fundamental properties of DNA and, due to the exquisite specificity of DNA-mediated charge transfer for the integrity of the π-stack, for use in next generation diagnostic sensing. Here, multiplexed DNA-modified electrodes are used to (i) gain new insights on the electrochemical coupling of metalloproteins to the DNA π-stack with relevance to the fundaments of in vivo DNA-mediated charge transfer and (ii) enhance the overall sensitivity of DNA-mediated reduction for use in the detection of low abundance diagnostic targets.

First, Methylene Blue (MB′) was covalently attached to DNA through a flexible C12 alkyl linker to yield a new redox reporter for DNA electrochemistry measurements with enhanced sensitivity. Tethered, intercalated MB′ was reduced through DNA-mediated charge transport. The redox signal intensity for MB′-dT-C12-DNA was found to be at least 3 fold larger than that of previously used Nile Blue (NB)-dT-DNA, which is coupled to the base stack via direct conjugation. The signal attenuation, due to an intervening mismatch, and therefore the degree of DNA-mediated reduction, does, however, depend on the DNA film morphology and the backfilling agent used to passivate the surface. These results highlight two possible mechanisms for the reduction of MB′ on the DNA-modified electrode that are distinguishable by their kinetics: reduction mediated by the DNA base pair stack and direct surface reduction of MB′ at the electrode. The extent of direct reduction at the surface can be minimized by overall DNA assembly conditions.

Next, a series of intercalation-based DNA-mediated electrochemical reporters were developed, using a flexible alkane linkage to validate and explore their DNA-mediated reduction. The general mechanism for the reduction of distally bound redox active species, covalently tethered to DNA through flexible alkyl linkages, was established to be an intraduplex DNA-mediated pathway. MB, NB, and anthraquinone were covalently tethered to DNA with three different covalent linkages. The extent of electronic coupling of the reporter was shown to correlate with the DNA binding affinity of the redox active species, supporting an intercalative mechanism. These electrochemical signals were shown to be exceptionally sensitive to a single intervening π-stack perturbation, an AC mismatch, in a densely packed DNA monolayer, which further supports that the reduction is DNA-mediated. Finally, this DNA-mediated reduction of MB occurs primarily via intra- rather than inter duplex intercalation, as probed through varying the proximity and integrity of the neighboring duplex DNA. Further gains to electrochemical sensitivity of our DNA-modified devices were then achieved through the application of electrocatalytic signal amplification using these solvent accessible intercalative reporters, MB-dT-C8, and hemoglobin as a novel electron sink. Electrocatalysis offers an excellent means of electrochemical signal amplification, yet in DNA based sensors, its application has been limited due to strict assembly conditions. We describe the use of hemoglobin as a robust and effective electron sink for electrocatalysis in DNA sensing on low density DNA films. Protein shielding of the heme redox center minimizes direct reduction at the electrode surface and permits assays on low density DNA films. Electrocatalysis of MB that is covalently tethered to the DNA by a flexible alkyl linkage allows for efficient interactions with both the base stack and hemoglobin. Consistent suppression of the redox signal upon incorporation of single CA mismatch in the DNA oligomer demonstrates that both the unamplified and the electrocatalytically amplified redox signals are generated through DNA-mediated charge transport. Electrocatalysis with hemoglobin is robust: it is stable to pH and temperature variations. The utility and applicability of electrocatalysis with hemoglobin is demonstrated through restriction enzyme detection, and an enhancement in sensitivity permits femtomole DNA sampling.

Finally, we expanded the application of our multiplexed DNA-modified electrodes to the electrochemical characterization of DNA-bound proteins containing [4Fe-4S] clusters. DNA-modified electrodes have become an essential tool for the characterization of the redox chemistry of DNA repair proteins that contain redox cofactors. Multiplexed analysis of EndonucleaseIII (EndoIII), a DNA repair protein containing a [4Fe-4S] cluster known to be accessible via DNA-mediated charge transport, elucidated subtle differences in the electrochemical behavior as a function of DNA morphology. DNA-bound EndoIII is seen to have two different electron transfer pathways for reduction, either through the DNA base stack or through direct surface reduction. Closely packed DNA films, where the protein has limited surface accessibility, produce electrochemical signals reflecting electron transfer that is DNA-mediated. The electrochemical comparison of EndoIII mutants, including a new family of mutations altering the electrostatics surrounding the [4Fe-4S] cluster, was able to be quantitatively performed. While little change in the midpoint potential was found for this family of mutants, significant variations in the efficiency of DNA-mediated electron transfer were apparent. Based on the stability of these proteins, examined by circular dichroism, we propose that the electron transfer pathway can be perturbed not only by the removal of aromatic residues, but also through changes in solvation near the cluster.

Randomness-efficient curve sampling

Curve samplers are sampling algorithms that proceed by viewing the domain as a vector space over a finite field, and randomly picking a low-degree curve in it as the sample. Curve samplers exhibit a nice property besides the sampling property: the restriction of low-degree polynomials over the domain to the sampled curve is still low-degree. This property is often used in combination with the sampling property and has found many applications, including PCP constructions, local decoding of codes, and algebraic PRG constructions.

The randomness complexity of curve samplers is a crucial parameter for its applications. It is known that (non-explicit) curve samplers using O(log N + log(1/δ)) random bits exist, where N is the domain size and δ is the confidence error. The question of explicitly constructing randomness-efficient curve samplers was first raised in [TU06] where they obtained curve samplers with near-optimal randomness complexity.

In this thesis, we present an explicit construction of low-degree curve samplers with optimal randomness complexity (up to a constant factor) that sample curves of degree (m log_q(1/δ))^O(1) in F_q^m. Our construction is a delicate combination of several components, including extractor machinery, limited independence, iterated sampling, and list-recoverable codes.

The power of quantum Fourier sampling

How powerful are Quantum Computers? Despite the prevailing belief that Quantum Computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's famous factoring algorithm [Shor97] gives an example of a problem that can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring, however, is unlikely to be NP-Hard, meaning that few unexpected formal consequences would arise, should such a classical algorithm be discovered. Could it then be the case that any quantum algorithm can be simulated efficiently classically? Likewise, could it be the case that Quantum Computers can quickly solve problems much harder than factoring? If so, where does this power come from, and what classical computational resources do we need to solve the hardest problems for which there exist efficient quantum algorithms?

We make progress toward understanding these questions through studying the relationship between classical nondeterminism and quantum computing. In particular, is there a problem that can be solved efficiently on a Quantum Computer that cannot be efficiently solved using nondeterminism? In this thesis we address this problem from the perspective of sampling problems. Namely, we give evidence that approximately sampling the Quantum Fourier Transform of an efficiently computable function, while easy quantumly, is hard for any classical machine in the Polynomial Time Hierarchy. In particular, we prove the existence of a class of distributions that can be sampled efficiently by a Quantum Computer, that likely cannot be approximately sampled in randomized polynomial time with an oracle for the Polynomial Time Hierarchy.

Our work complements and generalizes the evidence given in Aaronson and Arkhipov's work [AA2013] where a different distribution with the same computational properties was given. Our result is more general than theirs, but requires a more powerful quantum sampler.

Enhanced Thermoelectric Performance at the Superionic Phase Transitions of Mixed Ion-Electron Conducting Materials

The quality of a thermoelectric material is judged by the size of its temperature de- pendent thermoeletric-figure-of-merit (zT ). Superionic materials, particularly Zn₄Sb₃ and Cu₂Se, are of current interest for the high zT and low thermal conductivity of their disordered, superionic phase. In this work it is reported that the super-ionic materials Ag₂Se, Cu₂Se and Cu_1.97Ag_0.03Se show enhanced zT in their ordered, normal ion-conducting phases. The zT of Ag₂Se is increased by 30% in its ordered phase as compared to its disordered phase, as measured just below and above its first order phase transition. The zT ’s of Cu₂Se and Cu_1.97Ag_0.03Se both increase by more than 100% over a 30 K temperatures range just below their super-ionic phase transitions. The peak zT of Cu₂Se is 0.7 at 406 K and of Cu_1.97Ag_0.03Se is 1.0 at 400 K. In all three materials these enhancements are due to anomalous increases in their Seebeck coefficients, beyond that predicted by carrier concentration measurements and band structure modeling. As the Seebeck coefficient is the entropy transported per carrier, this suggests that there is an additional quantity of entropy co-transported with charge carriers. Such co-transport has been previously observed via co-transport of vibrational entropy in bipolaron conductors and spin-state entropy in Na_xCo₂O₄. The correlation of the temperature profile of the increases in each material with the nature of their phase transitions indicates that the entropy is associated with the thermodynamcis of ion-ordering. This suggests a new mechanism by which high thermoelectric performance may be understood and engineered.

Cavity-enhanced spectroscopies for applications of remote sensing, chemical kinetics and detection of radical species

This thesis describes applications of cavity enhanced spectroscopy towards applications of remote sensing, chemical kinetics and detection of transient radical molecular species. Both direct absorption spectroscopy and cavity ring-down spectroscopy are used in this work. Frequency-stabilized cavity ring-down spectroscopy (FS-CRDS) was utilized for measurements of spectral lineshapes of O₂ and CO₂ for obtaining laboratory reference data in support of NASA’s OCO-2 mission. FS-CRDS is highly sensitive (> 10 km absorption path length) and precise (> 10000:1 SNR), making it ideal to study subtle non-Voigt lineshape effects. In addition, these advantages of FS-CRDS were further extended for measuring kinetic isotope effects: A dual-wavelength variation of FS-CRDS was used for measuring precise D/H and ¹³C/¹²C methane isotope ratios (sigma>0.026%) for the purpose of measuring the temperature dependent kinetic isotope effects of methane oxidation with O(¹D) and OH radicals. Finally, direct absorption spectroscopic detection of the trans-DOCO radical via a frequency combs spectrometer was conducted in collaboration with professor Jun Ye at JILA/University of Colorado.

Metaconcrete: Engineered aggregates for enhanced dynamic performance

This work presents the development and investigation of a new type of concrete for the attenuation of waves induced by dynamic excitation. Recent progress in the field of metamaterials science has led to a range of novel composites which display unusual properties when interacting with electromagnetic, acoustic, and elastic waves. A new structural metamaterial with enhanced properties for dynamic loading applications is presented, which is named metaconcrete. In this new composite material the standard stone and gravel aggregates of regular concrete are replaced with spherical engineered inclusions. Each metaconcrete aggregate has a layered structure, consisting of a heavy core and a thin compliant outer coating. This structure allows for resonance at or near the eigenfrequencies of the inclusions, and the aggregates can be tuned so that resonant oscillations will be activated by particular frequencies of an applied dynamic loading. The activation of resonance within the aggregates causes the overall system to exhibit negative effective mass, which leads to attenuation of the applied wave motion. To investigate the behavior of metaconcrete slabs under a variety of different loading conditions a finite element slab model containing a periodic array of aggregates is utilized. The frequency dependent nature of metaconcrete is investigated by considering the transmission of wave energy through a slab, which indicates the presence of large attenuation bands near the resonant frequencies of the aggregates. Applying a blast wave loading to both an elastic slab and a slab model that incorporates the fracture characteristics of the mortar matrix reveals that a significant portion of the supplied energy can be absorbed by aggregates which are activated by the chosen blast wave profile. The transfer of energy from the mortar matrix to the metaconcrete aggregates leads to a significant reduction in the maximum longitudinal stress, greatly improving the ability of the material to resist damage induced by a propagating shock wave. The various analyses presented in this work provide the theoretical and numerical background necessary for the informed design and development of metaconcrete aggregates for dynamic loading applications, such as blast shielding, impact protection, and seismic mitigation.

High energy heavy ion induced enhanced adhesion

The work described in this thesis represents an attempt to summarize to date the information collected on the process of high energy heavy ion induced enhanced adhesion. Briefly, the process involves the irradiation of materials covered by thin (≾3μm) films with high energy (E > 200 keV I nucleon) heavy ion beams (such as Fluorine or Chlorine). Enhanced adhesion has been observed on all material combinations tested, including metal on metal, metal on semiconductor, metal on dielectric and dielectric on dielectric systems. In some cases, the enhancement can be quite large, so that a film that could be wiped off a substrate quite easily before irradiation can withstand determined scrubbing afterwards.

Very little is understood yet about this adhesion mechanism, so what is presented are primarily observations about systems studied, and descriptions of the actual preparation and irradiation of samples used. Some discussion is presented about mechanisms that have been considered but rejected.