M.Sc Thesis

M.Sc StudentSalhov Moshe
SubjectRobust Equalization and Multiuser Detection
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Yonina Eldar


The structured robust least squares (SRLS) method is a technique for solving a least squares (LS) problem when the problem model suffers from unknown but bounded perturbations with structure. The SRLS solution is optimal in a worst-case MinMax sense. There are many possible reasons for uncertainties in the problem model, for example: measurement error, and time variation of the model. The standard method for solving a SRLS problem is to solve a semidefinite programming (SDP) equivalent problem. An SRLS solution via SDP can be found by using a standard SDP solver, although when the problem dimensions are large, solving the SRLS problem via SDP may be suboptimal in a computational complexity sense. The focus of this thesis is the development of an efficient and practical algorithm that solves the SRLS problem, which has been generalized to have sphere constraints on the vector of unknowns. The SRLS optimization problem is a convex MinMax problem. Furthermore, the inner maximization is not a smooth function, therefore standard gradient methods are not applicable. We base the new design on a method of subgradients. The new method is justified by Danskin's MinMax theorem, and enjoys the well-known convergence properties of the subgradient method. In order to specify the optimization scheme we detail the calculation of the initial starting point, the construction of the subgradient based on solving a trust region subproblem, the step size rule and the stopping criteria. In order to analyze the advantage of the suggested algorithm, we focus on measuring the number of arithmetic operations. Analyzing the number of arithmetic operations of the subgradient method and the SDP-based SRLS technique shows, that when the number of equations in the linear model is larger than the number of variables and larger than the number of uncertainty matrices, the subgradient scheme is more efficient, in terms of the number of arithmetic operations, than the SDP-based scheme. We verify by simulations the advantage of the suggested subgradient scheme. In the simulation we measure the average CPU time that is needed for designing the robust MMSE equalizer. Our simulations' results show that when the desired accuracy of the sphere-constrained SRLS solution is in the order of two digits, the subgradient method is more efficient in terms of the number of arithmetic operations compared with the SDP-based scheme. In this work we also consider the application of robust multiuser detection under the structured uncertainty model.