Subset selection in signal processing using sparsity-inducing norms

Abstract

This dissertation deals with different subset selection problems in wireless communications systems. These type of problems have a combinatorial nature, which makes them computationally intractable for medium and large-scale sizes. In particular, two different types of problems are addressed in this thesis: cardinality minimization and cardinality-constrained problems. Different mathematical relaxations are proposed with the aim of obtaining algorithms that approximately solve the proposed problems with a tractable computational cost. The first part of the dissertation deals with the angle of arrival estimation in an antenna array and falls within the so-called sparse signal representation framework. A simple, fast and accurate algorithm is proposed for finding the angles of arrival of multiple sources that impinge on an array of antennas. In contrast to other methods in the literature, the considered technique is not based on ad-hoc hyperparameters and does not require the previous knowledge of the number of incoming sources or a previous initialization. The second part of the thesis addresses the selection of the appropriate subset of cooperative nodes in dense relay-assisted wireless networks and constitutes the main focus of the research activities carried out in this thesis. In order to cope with the huge data traffic in the next generation of wireless networks, the number of access nodes and communication links will be densified, having as a result, an increase of the network complexity and its optimization. Within this framework, subset selection problems naturally arise to reduce the overall system management. The activation of many relay links, in dense relay-assisted wireless networks, is impractical due to the communications and processing overhead required to maintain the synchronization amongst all the spatially distributed nodes in the wireless network, which makes the network complexity unaffordable. The selection of the most suitable subset of spatially distributed relays in this context, is a key issue, since it has a dramatic effect in the overall system performance. In particular, the thesis addresses the joint distributed beamforming optimization and relay subset assignment in a multi-user scenario with non-orthogonal transmission and in a scenario with a single source-destination pair. Different design criteria are analyzed, all of them lead to challenging combinatorial nonlinear problems, which are non-convex and non-smooth. Dealing with the multiple relay selection in an ad-hoc wireless network with one source-destination, a new algorithm is proposed for finding the best subset of cooperative relays, and their beamforming weights, so that the SNR is maximized at the destination terminal. This problem is addressed taking into account per-relay power constraints and second-order channel state information. In this context, a sub-optimal method, based on a semidefinite programming relaxation, is proposed. It achieves a near-optimal performance with a reduced computational complexity. The joint relay assignment and distributed beamforming optimization in multi-user wireless relay networks deserves a special attention. Two major problems are addressed: i) the selection of the minimum number of cooperative nodes that guarantees some predefined Quality of Service (QoS) requirements at the destination nodes and; ii) the selection of the best subset of K relays that minimizes the total relay transmit power, satisfying QoS constraints at the destinations. The mathematical formulations of these problems involve non-convex objective functions coupled with non-convex constraints. They are fit into the DC optimization framework and solved using novel path-following methods based on the penalty convex-concave procedure. The proposed techniques exhibit a low complexity and are able to achieve high-quality solutions close to the global optimum.

Esta tesis aborda diversos problemas de selección de subconjuntos en comunicaciones inalámbricas. Este tipo de problemas tiene una naturaleza combinatoria que los hace computacionalmente intratables. En concreto, se consideran dos tipos de problemas: i) la minimización de la cardinalidad y ii) la optimización de problemas con restricciones de cardinalidad. Se proponen diversas relajaciones matemáticas, con el fin de desarrollar algoritmos capaces de obtener un rendimiento casi óptimo y una baja complejidad computacional. La primera parte de la tesis se centra en el problema de estimación de los ángulos de llegada en una agrupación de antenas y se enmarca dentro de los llamados problemas de representación sparse. En este contexto, se propone un algoritmo rápido, preciso y simple para la estimación de las direcciones de llegada en una agrupación de antenas. Al contrario que otras técnicas en la literatura, el método propuesto, no se basa en hiperparámetros y no requiere el conocimiento a priori del número de fuentes o una inicialización previa. La segunda parte de la tesis aborda el problema de selección del mejor subconjunto de nodos cooperativos en una red densa de relays inalámbricos. Con el fin de lidiar con el inmenso tráfico de datos en las próximas generaciones de redes inalámbricas, la densidad del número de puntos de acceso y de conexiones aumentará, teniendo como resultado un incremento de la complejidad de la red y de su optimización. Dentro de este marco, los problemas de selección de subconjuntos aparecen de modo natural con el fin de reducir la complejidad de la gestión de la red. La activación de un gran número de terminales, en redes densas de nodos cooperativos, no es factible debido al gran intercambio de información adicional que se requiere entre los terminales, que se encuentran espacialmente distribuidos en diferentes localizaciones. En este contexto, la selección del mejor subconjunto de estos nodos es de gran importancia dado el elevado impacto que tiene en el rendimiento del sistema. Esta tesis aborda la optimización conjunta del conformador de haz (beamformer) y la selección del mejor subconjunto nodos en diversos escenarios cooperativos. Se analizan diversos criterios de diseño, todos ellos conducen a complejos problemas combinatorios no lineales y no convexos. Dentro del contexto de la selección de múltiples nodos en redes inalámbricas cooperativas con un par origen-destino, se propone un algoritmo para encontrar el mejor subconjunto de terminales cooperativos y sus respectivos pesos, de manera que la SNR se maximice en el nodo de destino. Este problema se trata teniendo en cuenta restricciones individuales de potencia en los nodos cooperativos e información estadística de segundo orden de los canales inalámbricos de la red. En este contexto, se presenta un algoritmo con una baja complejidad y un rendimiento cercano al óptimo. La optimización conjunta de los pesos del conformador distribuido y la selección del subconjunto de nodos cooperativos en redes inalámbricas multiusuario merece una atención especial. En esta tesis se abordan dos problemas relevantes: 1) la selección del mínimo número de nodos cooperativos capaces de garantizar una cierta calidad de servicio en los nodos destino y; 2) la selección del mejor subconjunto de K terminales repetidores que minimiza la potencia total transmitida, cumpliendo con ciertas restricciones de calidad de servicio en los nodos destino. La formulación matemática de estos problemas involucra funciones objetivo no convexas acopladas con restricciones que tampoco son convexas. Para aliviar la elevada complejidad de estos problemas se proponen nuevos algoritmos con una baja carga computacional y un rendimiento casi óptimo.