In this thesis, we investigate and design new optimization techniques and algorithms to promote the target signal structures in their estimation/recovery process from an ill-posed linear system of equations. In particular, we consider wireless time-varying channels estimation problem and image/video signals acquisition problem from a small set of measurements. ? We present our proposed approaches to estimate two-dimensional (2D), time-varying, wireless communication channels by promoting their prior physical structures. We show that geometric information and intrinsic sparse structures of wireless communication channels can be exploited via proper regularization functions in the estimation problem to improve the accuracy of channel estimation with modest computational complexity. In particular, we studied the channel estimation problem for vehicle-to-vehicle (V2V), underwater acoustic (UWA) communication channels, and leaked time-varying narrowband communication channels. ? We show that V2V channels have a joint element- and group-wise sparsity structures. To exploit these structures, we propose a nested joint sparse recovery method. Our method solves the joint element/group sparse channel (signal) estimation problem using the proximity operators of a broad class of regularizers based on the alternating direction method of multipliers. Furthermore, key properties of the proposed objective functions are proven which ensure that the optimal solution is found by the new algorithm. We also investigate the underwater channel estimation problem. The underwater channel can be represented by a multi-scale multi-lag (MSML) channel model. We show that the data matrix for the transmitted signal, after passing through the MSML channel, exhibits a low-rank representation. In addition, we show that the MSML channel estimation problem can be represented as a spectral estimation problem. By exploiting the intrinsic low-rank structure of the received signal, the Prony algorithm is adapted to estimate the Doppler scales (close frequencies), delays and channel gains. Two strategies using convex and non-convex regularizers to remove noise from the corrupted signal were proposed. A bound on the reconstruction of the noise-less received signal provides guidance on the selection of the relaxation parameter in the convex optimizations. Another interesting problem is the estimation of a narrowband time-varying channel under the practical assumptions of finite block length and finite transmission bandwidth is investigated. We show that the signal, after passing through a time-varying narrowband channel reveals a particular parametric low-rank structure that can be represented as a bilinear form. To estimate the channel, we propose two structured methods. The first method exploits the low-rank bilinear structure of the channel via a non-convex strategy based on alternating direction optimization between delay and Doppler directions. Due to the non-convex nature of this approach, it is sensitive to local minima. Motivated by this issue, we propose a novel convex approach based on the minimization of the atomic norm using measurements of the signal at time domain. Furthermore, for convex approach, we characterize the optimality and uniqueness conditions, and theoretical guarantee for the noiseless channel estimation problem with a small number of measurements. ? In the next part of this thesis, we consider employing a compression code to build an efficient (polynomial time) compressed sensing recovery algorithm. Modern image and video compression codes employ elaborate structures in an effort to encode them using a small number of bits. Compressed sensing recovery algorithms, on the other hand, use such structures to recover the signals from a few linear observations. Despite the steady progress in the field of compressed sensing, the structures that are often used for signal recovery are still much simpler than those employed by state-of-the-art compression codes. The main goal of our study is to bridge this gap by answering the following question: Can one employ a compression code to build an efficient (polynomial time) compressed sensing recovery algorithm? In response to this question, the compression-based gradient descent (C-GD) algorithm is proposed. C-GD, which is a low-complexity iterative algorithm, is able to employ a generic compression code for compressed sensing and therefore enlarges the set of structures used in compressed sensing to those used by compression codes. We provide a convergence analysis of C-GD, a characterization of the required number of samples as a function of the rate-distortion function of the compression code