In a series of work initiated by Nemirovsky and Yudin, and later extended by Nesterov, first-order algorithms for unconstrained minimization with optimal theoretical complexity bound have been proposed. On the other hand, conjugate gradient algorithms as one of the widely used first-order techniques suffer from the lack of a finite complexity bound. In fact their performance can possibly be quite poor. This dissertation is partially on tightening the gap between these two classes of algorithms, namely the traditional conjugate gradient methods and optimal first-order techniques. We derive conditions under which conjugate gradient methods attain the same complexity bound as in Nemirovsky-Yudin's and Nesterov's methods. Moreover, we propose a conjugate gradient-type algorithm named CGSO, for Conjugate Gradient with Subspace Optimization, achieving the optimal complexity bound with the payoff of a little extra computational cost. We extend the theory of CGSO to convex problems with linear constraints. In particular we focus on solving $l_1$-regularized least square problem, often referred to as Basis Pursuit Denoising (BPDN) problem in the optimization community. BPDN arises in many practical fields including sparse signal recovery, machine learning, and statistics. Solving BPDN is fairly challenging because the size of the involved signals can be quite large; therefore first order methods are of particular interest for these problems. We propose a quasi-Newton proximal method for solving BPDN. Our numerical results suggest that our technique is computationally effective, and can compete favourably with the other state-of-the-art solvers.

Ultra-wideband (UWB) technology is the next viable solution for applications in wireless personal area network (WPAN), body area network (BAN) and wireless sensor network (WSN). However, as application evolves toward a more realistic situation, wideband channel characteristics such as pulse distortion must be accounted for in channel modeling. Furthermore, application-oriented services such as ranging and localization demand fast prototyping, real-time processing of measured data, and good low signal-to-noise ratio (SNR) performance. Despite the tremendous effort being vested in devising new receivers by the global research community, channel-estimating Rake receiver is still one of the most promising receivers that can offer superior performance to the suboptimal counterparts. However, acquiring Nyquist-rate samples costs substantial power and resource consumption and is a major obstacle to the feasible implementation of the asymptotic maximum likelihood (ML) channel estimator. In this thesis, we address all three aspects of the UWB impulse radio (UWB-IR), in three separate contributions. First, we study the {\it a priori} dependency of the CLEAN deconvolution with real-world measurements, and propose a high-resolution, multi-template deconvolution algorithm to enhance the channel estimation accuracy. This algorithm is shown to supersede its predecessors in terms of accuracy, energy capture and computational speed. Secondly, we propose a {\it regularized} least squares time-of-arrival (ToA) estimator with wavelet denoising to the problem of ranging and localization with UWB-IR. We devise a threshold selection framework based on the Neyman-Pearson (NP) criterion, and show the robustness of our algorithm by comparing with other ToA algorithms in both computer simulation and ranging measurements when advanced digital signal processing (DSP) is available. Finally, we propose a low-complexity ML (LC-ML) channel estimator to fully exploit the multipath diversity with Rake receiver with sub-Nyquist rate sampling. We derive the Cram\'er-Rao Lower Bound (CRLB) for the LC-ML, and perform simulation to compare our estimator with both the $\ell_1$-norm minimization technique and the conventional ML estimator.