Estimating the underlying parameters of a statistical signal from noisy observations is a central problem in signal processing, with a wide variety of applications in many different fields such as machine learning, source localization, channel estimation for modern millimeter-wave (mmWave) communication systems, etc. Classical algorithms for source localization guarantee recovery of only $K=\mathcal{O}(M)$ sources using a Uniform Linear Array equipped with $M$ antennas. Recently, it has been shown that using certain non-uniform array designs, such as coprime and nested arrays, once certain correlation priors are assumed, it is possible to break this limit and go all the way up to $K=\mathcal{O}(M^2)$ sources. This thesis sheds more light on this phenomena, and more general cases of under-determined inverse problems in both linear, and non-linear settings. We show that for linear inverse problems, not only CRB exists for the case that $K=\mathcal{O}(M^2)$, for certain non-uniform arrays, but also it continues to exist even if the antenna locations are perturbed due to physical deformation of the device, or only a compressed version of the measurements are available. For a more general class of linear inverse problems, we show that in presence of certain correlation priors, one can recover sparse vectors of sparsity $K=\mathcal{O}(M^2)$, where the probability of detecting a wrong support for the sparse vector decays to zero exponentially fast as more and more temporal snapshots are obtained. We show these results hold for a variety of different statistical models, namely Gaussian sources, bounded sources, when the measurement matrices are equi-angular tight frames, and finally for the case that the measurements are obtained in adaptively. This thesis also considers multilinear inverse problems, namely tensor decompositions as well as certain non-convex problems with applications in millimeter-wave (mmWave) communication systems. We propose tensor decomposition algorithms for channel estimation for mmWave communication systems equipped with hybrid analog/digital beamforming, for cases such as multi-carrier Single-Input/Multiple-Output and single-carrier Multiple-Input/Multiple-Output, where we show the immense benefit gained by posing certain commonly considered statistical assumptions on the channel parameters, which leads to a provable increased identifiability compared to the existing algorithms for mmWave channel estimation.

Sub-Nyquist sampling has received a huge amount of interest in the past decade. In classical compressed sensing theory, if the measurement procedure satisfies a particular condition known as Restricted Isometry Property (RIP), we can achieve stable recovery of signals of low-dimensional intrinsic structures with an order-wise optimal sample size. Such low-dimensional structures include sparse and low rank for both vector and matrix cases. The main drawback of conventional compressed sensing theory is that random measurements are required to ensure the RIP property. However, in many applications such as imaging and array signal processing, applying independent random measurements may not be practical as the systems are deterministic. Moreover, random measurements based compressed sensing always exploits convex programs for signal recovery even in the noiseless case, and solving those programs is computationally intensive if the ambient dimension is large, especially in the matrix case.

The main contribution of this dissertation is that we propose a deterministic sub-Nyquist sampling framework for compressing the structured signal and come up with computationally efficient algorithms. Besides widely studied sparse and low-rank structures, we particularly focus on the cases that the signals of interest are stationary or the measurements are of Fourier type. The key difference between our work from classical compressed sensing theory is that we explicitly exploit the second-order statistics of the signals, and study the equivalent quadratic measurement model in the correlation domain. The essential observation made in this dissertation is that a difference/sum coarray structure will arise from the quadratic model if the measurements are of Fourier type. With these observations, we are able to achieve a better compression rate for covariance estimation, identify more sources in array signal processing or recover the signals of larger sparsity.

In this dissertation, we will first study the problem of Toeplitz covariance estimation. In particular, we will show how to achieve an order-wise optimal compression rate using the idea of sparse arrays in both general and low-rank cases. Then, an analysis framework of super-resolution with positivity constraint is established. We will present fundamental robustness guarantees, efficient algorithms and applications in practices. Next, we will study the problem of phase-retrieval for which we successfully apply the sparse array ideas by fully exploiting the quadratic measurement model. We achieve near-optimal sample complexity for both sparse and general cases with practical Fourier measurements and provide efficient and deterministic recovery algorithms. In the end, we will further elaborate on the essential role of non-negative constraint in underdetermined inverse problems. In particular, we will analyze the nonlinear co-array interpolation problem and develop a universal upper bound of the interpolation error. Bilinear problem with non-negative constraint will be considered next and the exact characterization of the ambiguous solutions will be established for the first time in literature. At last, we will show how to apply the nested array idea to solve real problems such as Kriging. Using spatial correlation information, we are able to have a stable estimate of the field of interest with fewer sensors than classic methodologies. Extensive numerical experiments are implemented to demonstrate our theoretical claims.

High dimensional inverse problems are at the heart of numerous modern signal processing and machine learning applications, where the goal is to sense the physical environment and infer parameters of interest residing in a high-dimensional ambient space, from low-dimensional (non)-linear measurements. Despite the rapid growth in the volume of data that is being generated in the form of images, videos, and sensors, there are restrictions imposed by the physical constraints of the sensing system. For instance, in a scanning microscopy system, the frame rate and hence the temporal resolution is limited by the speed of the scanning mirrors and the size of the field of view (FOV). Similarly, in the modern hybrid mmWave systems, although a massive number of antennas are deployed, the number of Radio Frequency (RF) chains is scarce due to their high cost and power consumption. Therefore, it is crucial to design sensing paradigms that can reliably recover the information of interest under such stringent sampling budgets. This requires leveraging the underlying ``low-dimensional" geometry of the signal (known as priors) to enable reconstruction with relatively few measurements. Over the last two decades, several theoretical and algorithmic techniques have been developed for tackling these under-determined systems, the most well-known among them being sparse and low-rank signal/image reconstruction.

In this thesis, we primarily focus on the ``ill-posed" inverse problem of super-resolution with ``extreme spatial/temporal sampling constraints" arising from real-world applications in Neural Spike Deconvolution and Sensor Array Signal Processing. We especially focus on unconventional regimes where existing approaches based on {sparsity, correlation and/or low rank} priors may fail. Broadly, super-resolution is concerned with the reconstruction of temporally/spatially localized events (or spikes) from samples of their convolution with a low-pass filter. The problem becomes ill-posed due to systematic attenuation of the high-frequency content of the underlying spikes. Unlike classical compressed sensing, the under-sampling operation in super-resolution does not correspond to observing random linear projections of the unknown signal of interest. This prevents direct application of existing theoretical guarantees developed in the compressed sensing literature. In contrast to prior works in super-resolution which exploit the role of sparsity and/or non-negativity priors to solve the resulting ill-posed problem, this thesis explores the problem of Binary Super-resolution, i.e., when the spike amplitudes are known apriori to be binary-valued. We demonstrate that enforcing binary priors in under-determined linear inverse problems can allow exact recovery (in absence of noise) in the non-standard regime where the sparsity level of the spikes far exceeds the number of acquired measurements --- which henceforth is referred to as ``extreme compression" regime. Past works have shown that it is possible to operate in such a regime by leveraging multiple snapshots and statistical priors. On the contrary, this thesis shows that multiple measurements may not be necessary to operate in extreme compression in the face of binary constraints. We also show that standard convex-relaxation techniques for the binary constraint, such as box-constraints (that are widely used in Binary compressed sensing), are inadequate for operating in extreme compression regimes and they can introduce a certain bias in the support of the recovered spikes. We overcome the computational challenges of enforcing binary constraints by exploiting the special structure of the measurements that allow us to reformulate the problem as a binary search.

Despite the ability to recover finite-valued signals from uniformly downsampled measurements for most filters, there might exist certain ``adversarial filters" that result in ambiguity upon uniform downsampling. We exhibit that the additional flexibility of designing the measurement matrix (beyond uniform-sampling) can mitigate the effects of adversarial filters. We propose a novel algorithm-measurement co-design framework where the measurement matrix is designed as a function of the filter. In absence of noise, this framework can provably achieve the optimal complexity, which is independent of dimension as well as sparsity of the binary signal. Moreover, the recovery can be performed using a greedy sequential decoding algorithm with low computational complexity.

The second half of this dissertation studies another class of problems with stringent requirements on available spatial and temporal measurements. This problem arises in passive sensing scenarios with sparse sensor arrays, where the goal is to perform source localization with very few spatial sensors. Sparse array geometries such as nested arrays and co-prime arrays have gained popularity due to their ability to identify more sources than sensors and offer very high resolution compared to a uniform array with the same number of physical sensors. The benefit is attributed to the ability of sparse arrays to exploit certain correlation structures in the source signals, without increasing the spatial sensing budget. However, it is commonly believed that sparse arrays inherently require a large number of temporal snapshots to obtain reliable correlation estimation, and therefore, they may not be preferred in the so-called “sample-starved” regimes, where the temporal snapshots are scarce. In applications like automotive radar and mmWave communication systems, the sources/multipaths may be coherent and the environment is dynamic due to the high mobility of the sources. Motivated by these challenging scenarios, it is desirable to identify the sources or multipath components with superior resolution while using very few temporal snapshots (only a single snapshot in the extreme case). The techniques developed in these sample-starved scenarios are largely based on heuristics. This thesis debunks some of the myths associated with sparse arrays in the limited snapshot regime by providing provable ways to leverage benefits of deterministic sparse arrays (nested arrays) in the following largely unexplored regimes: (i) with few snapshots (of the order of number of sources) and (ii) extreme-sample starved scenarios with only a single snapshot.

Sensing plays a vital role in modern technology, particularly in communications, automotive radar, and remote sensing. One of the main restrictions in sensing systems is identifying the parameters of interest with limited resources like power and sensor numbers by leveraging prior knowledge about signals to capture only a portion of high-dimensional data. This dissertation focuses on two foundational principles: sparse sampling geometries for data collection and algorithms for solving inverse problems to extract desired information from these measurements.

The first part of the dissertation examines the superiority of sparse sensing strategies in source localization tasks under strict time snapshot and sensor constraints. Key contributions include a rigorous non-asymptotic analysis of the Coarray ESPRIT algorithm, demonstrating that sparse arrays maintain high resolution and accuracy even with limited temporal snapshots compared to traditional uniform sensing geometries. The dissertation also analyzes an interpolation technique for array synthesis under single snapshot and positive source conditions, showing that sparse arrays can be effectively used by solving a simple convex feasibility search problem. Additionally, the research provides minimax error rates, comparing the performance of ULAs and nested arrays, and establishing theoretical bounds that demonstrate the superiority of sparse arrays and validate the empirical advantages of sparse arrays. The study also examines random sparse arrays, proposing new sampling schemes to ensure large contiguous coarrays, which are crucial for effective sensing.

Beyond array signal processing, the dissertation extends the analysis of these spatio-temporal tradeoffs to other non-linear inverse problems. It introduces Khatri-Rao dictionary learning for tensor data, demonstrating global identifiability and providing sample complexity bounds. Furthermore, it explores the training of polynomial neural networks via low-rank tensor recovery, proposing a novel iterative algorithm that improves efficiency and generalizes previous approaches. Lastly, it addresses the joint support recovery of sparse vectors from 1-bit measurements, offering an adaptive method that operates effectively in extreme spatial compression regimes.

Inverse problems in high-dimensional spaces are central to fields like signal processing, wireless communication, and machine learning. These problems involve inferring parameters of interest in high-dimensional ambient spaces from low-dimensional (non-)linear measurements. Despite advances in sensing systems, real-world inverse problems remain challenging due to physical constraints, making them inherently ill-posed. Exploiting low-dimensional structures, or priors, is critical to make these problems well-posed. Structural priors like sparsity have been widely used for regularization, while recent advances have introduced data-driven priors that capture more intricate structures.

This dissertation first explores structural priors, focusing on joint support recovery, an important problem in applications such as source localization and sparse spectrum sensing. We present Adaptive Joint Support Recovery (Ada-JSR), an adaptive strategy that enables exact support recovery under extreme compression, requiring only one measurement per unknown vector.

We then propose a data-driven approach to joint support recovery by unrolling the Iterative Shrinkage Thresholding Algorithm (ISTA) for correlation-aware support recovery. This method maintains the structural integrity of the physical model and achieves support recovery with fewer measurements in noisy settings, even in the presence of model mismatch.

Next, we address channel sensing in mmWave systems, focusing on the beamspace ESPRIT algorithm. We provide a non-asymptotic analysis and propose a max-min criterion for beamformer design, improving mmWave channel estimation algorithms, including beamspace ESPRIT.

Additionally, we tackle the super-resolution problem, recovering fine details from low-resolution measurements. We characterize super-resolution error bounds for unbiased estimators across various sensor array geometries in low SNR scenarios. Specifically, we demonstrate that nested arrays outperform uniform linear arrays (ULA) in resolving closely spaced sources, offering lower Cramér-Rao Bounds (CRB) in such conditions.

Finally, we explore data-driven priors, leveraging generative networks to regularize inverse problems. We study the interplay between generative priors, sensing operators, and training data, providing achievability guarantees of sample complexity bounds and proposing novel sensing strategies. An adaptive sensing strategy exploiting latent space partitions of ReLU networks is introduced, achieving exact signal recovery in noise-free settings. This work highlights how geometry-informed sensing design can balance computational and sample complexities while ensuring high performance, advancing both theory and practical applications in inverse problems.

Fluorine-19 MRI is an emerging technique offering specific detection of labeled cells in vivo. Lengthy acquisition times and modest signal-to-noise ratio (SNR) makes 3D spin-density weighted 19F imaging challenging. Importantly, recent innovations in molecular 19F tracer design and image acquisition-reconstruction methods have achieved significant leaps in 19F MRI sensitivity, and integration of these new materials and methods into studies can result in > 10-fold improvement in detection sensitivity. These developments may help unlock the full potential of clinical 19F MRI for cellular imaging applications, under the considerations of systematic measurement-algorithmic signal processing pillar.

The overarching goal of this dissertation is to investigate joint acquisition-reconstruction imaging techniques with enhanced detection through the lens of 19F cellular MRI. This in- cludes theoretical signal processing development perspective, pulse sequence programming, and reconstruction software workflow implementation on the MRI scanner. We start with the introduction of sensitivity analysis dependent on the LOD and theoretical MR signal modeling. Given that 19F-MRI generally involves the detection and localization of low concentrations of 19F-containing compounds, many signal averages are required to achieve acceptable SNR. Since sensitivity is governed by SNR/time, we focus on integrating spin physics and/or chemical domain knowledge into the systematic pulse sequence and reconstruction algorithm co-design for accelerated 19F MRI. To further enhance the sensitivity of paramagnetic metallo-PFC (MPFC), we describe a compressed sensing scheme, implemented using a novel ultrafast 3D radial pulse sequence, with data reconstructed via a hand-crafted sparsity-promoting algorithm. Combined with recent innovations in physics-driven deep learning, we exploit deep unrolling of radial chemical shift deconvolution arisen from 19F multiple cell targets detection tasks. Unlike typical 1H water-fat separation, large chemical frequency shifts in 19F cellular MRI provides new avenue to model the chemcial offsets and enable artifact-free separation under adverse data scenarios. Finally, we explore generative priors for a preliminary study in cellular MRI detection under high compression and low SNR regime and shed light on future research directions involving active sensing and self-supervised reconstruction for cellular MRI applications. All the techniques studied in this dissertation can be readily generalize to similar X-nuclei applications such as 23Na without any particular restrictions.