Orthogonal Matching Pursuit

Keywords: ADC Analog to Digital Converter, AIC Analog to Information Converter, AMP Approximate Message Passing, AST Affine Scaling Transformation, AWGN Additive White Gaussian Noise, BAOMP Back-tracking based Adaptive Orthogonal Matching Pursuit, BCS Bayesian Compressive Sensing, BP Basis Pursuit, BPDN BP de-noising, CIR Channel Impulse Response, CNN Convolutional Neural Network, CoSaMP Compressive Sampling Matching Pursuit, CP Chaining Pursuit, CR Cognitive Radio, CS Compressive Sensing DnCNN Denoising Convolutional Neural Network ECG Electrocardiogram, EM Expectation-Maximization, FBP Forward-Backward Pursuit, FISTA Fast Iterative Shrinkage Thresholding Algorithm, FOCUSS Focal Underdetermined System Solution, FPGA Field Programmable Gate Array, GBP Greedy Basis Pursuit, GOAMP Generalized Orthogonal Adaptive Matching Pursuit, GOMP Generalized Orthogonal Matching Pursuit

Communication channels are used to transmit information signals. However, these channels can cause several distortions on the signal to be transmitted, such as attenuation, multipath loss and Doppler shift, among others. For a better message recovery, the receiver can estimate the channel and bring more reliability to the communications systems.

Several communications systems, for example high-definition television, mmWave system, wideband HF and ultra-wideband have sparse channels. This characteristic can be used to improve the performance of the estimator and reduce the size of the training sequence so decreasing the consumption power and bandwidth. This thesis handles the channel estimation problem by investigating methods that exploit the sparsity of the channel. The study of Compressive Sensing and its sparse recovery algorithms led to the proposition of a new algorithm called Matching Pursuit based on Least Square (MPLS).

The use of neural networks (NN) to sparse signals estimation was also explored. The work focused on NN inspired by sparse recovery algorithms such as Learned Iterative Shrinkage-Thresholding Algorithm (LISTA). This resulted in two approaches that improve LISTA performance as well as to a new neural network suitable to estimate sparse signals.

people are very important to me but not the only ones. I would like you to know that even though you have not been mentioned here I am very grateful for all the help you have given me. I would like to deeply thank my husband, friend and companion Nilson for all support, love and patience over all these years. Especially during this period of the doctorate. This doctorate would never have started and it would have been impossible to finish it without his help both personally and intellectually. Thank you so much for sharing life with me and supporting me unconditionally.

I want to thank my parents, my sister, my grandmothers, my aunt, and all my family for their constant support, love, and encouragement. They have always been here for me, despite the physical distance. The ocean away did not prevent you from ever being present in my thoughts.

I would like to express my deep gratitude to Professeur Lírida Naviner for giving me the opportunity to pursue my internship in 2009 and now my PhD under her supervision. She has always been much more than a supervisor. Even in busy times, she has always supported me unconditionally. Thank you so much for these years of learning both in the professional and personal fields. Thank you for all the support and trust, for all the help before and during this thesis.

My sincere thanks also to Hao Cai for his support during my thesis. I would also like to express my acknowledgements to all the jury members: Hassan Aboushady, Jacques-Olivier Klein, Pietro Maris Ferreira, and Raimundo Carlos Silvério Freire for accepting to be part of my PhD committee and for the time and attention dedicated to read this manuscript and their remarks. In particular to Hassan Aboushady and Raimundo Carlos Silvério Freire for agreeing to be the reviewers of this dissertation. Thanks also to Hassan Aboushady and Pietro Maris Ferreira to be part of my mi-parcours.

Coming to Télécom Paris and being a PhD. student here was an incredible experience. I have always felt welcome here. Thanks to everyone I met at Télécom Paris as well as everyone who even not knowing personally allows this place to be a place of sharing knowledge and experience of different life and cultures in a pleasant way. Doing my doctorate at Télécom Paris gave me very happy moments, knowledge and new friendships. Thanks to the COMELEC department for welcoming me, especially to the SSH group for the great working environment.

I would like to thank as well Alain Sibille, Florence Besnard, Hamidou, Karim, and Marianna Baziz for making my stay at Télécom Paris so memorable. You helped me so much with bureaucracy and so many other things. Thank you so much Chantal Cadiat and Yvonne Bansimba not only for helping with the bureaucracies but especially for the countless conversations and laughter.

Thanks also to the teachers Sophie P. and Véra D. for their great and fun English classes. Furthermore, many thanks to all the colleagues and friends who shared the office with me and also those I met at Télécom Paris. Sharing my daily routine with you was very rewarding. Thanks for the discussions, lunches, coffee and all the great moments we spent together inside and outside Télécom Paris. Special thanks to Akram, Amir, Bader, Camille P., Daniel, Etienne, Lucas, Fábio, Francisco, Gabriel, Ganesh, Homa, Imene, Juan, Maha, Maarouf, Maurício, Mehrasa, Michele N., Moemoea, Natasha, Patrick, Pedro, Phu, Rafael, Sahar, Soumaya, You, and Xuecan.

Coming to Paris to do my PhD was also an opportunity to meet and live closer with friends I already knew. Thank you so much for your support since the day I arrived and for all the moments we spent together. It was great to live closer with you. In addition, during this period in Paris I have been gifted with new friendship. The moments we spent together will be forever in my memory. In particular, thanks to Adriana, Alexandre, Anderson, Andréa, Anne, Benjamin, Bruno, Camille E., Camille N., Chen, Christine, Éric, Eva, Flávia, Héctor, Jean-François, Julie G., Julie M., Julie T., Léa D., Léa M., Mengqi, Monique, Nardjesse, Pamela, Sara, Sophie N., and Thayane.

Thanks also to my colleagues and friends who stayed in Brazil. Your support before and during the doctorate was very important to me. Thank you for the countless conversations and cheering.

In particular my thank you very much to: Anna, Camila, Caio, Ernesto, Jacques, Luciana, Marta, Michele D., Priscila, Raquel, Renato, and Verdenia. I would also like to thank the support of the Brazilian government and all the people involved.

I will always remember this period that I lived with all of you. I hope to meet you again several times whether in Paris, Brazil or anywhere in the world.

I couldn't have done this without all of you. Thank you very much!

Table of Contents

List of Tables

List of Notation

( • ) H hermitian transpose ( • ) T transpose ( • ) † pseudo-inverse ( • ) -1 inverse µ( • ) coherence || • || p l p norm -||x|| p = (∑ n i=1 |x i | p ) 1/p
x(i) i th element of the vector x x i vector x at iteration/layer i A(Λ i ) submatrix of A containing only those columns of A with indices in Λ i h N × 1 sparse signal vector to be estimated ĥ estimate of h y M × 1 received signal vector

Introduction

This chapter introduces the reader to the context of this thesis and outlines the motivation and contributions of the present work.

Motivations

In the last decades, the development of technological solutions in communications has given rise to a new radio concept called Software Defined Radio (SDR) [START_REF] Mitola | SDR architecture refinement for JTRS[END_REF]. It is an emerging technology in which previously hardware-based features have become software-defined, enabling users to enter new applications when using an SDR. It presents several advantages for the development of wireless solutions in civil and military communications such as interoperability between troops of different forces and nations, the portability of waveforms, and the possibility of updating with the latest advances in radio communications without requiring a new hardware.

Transmitter Receiver Channel

Transmitted signal

Received signal Figure 1.1 -Elements of a communication system.

A communication system is basically composed of three elements: transmitter, channel and receiver as shown in Fig. 1.1 [START_REF] Haykin | Adaptive filter theory[END_REF]. Communications channels can cause several distortions on the signal, such as attenuation, multipath loss and Doppler shift, among others [START_REF] Haykin | Adaptive filter theory[END_REF]. Consequently, to better recover the message sent by the transmitter, an estimate of the channel can be used to compensate these effects, resulting in an accurate signal demodulation, equalization, and decoding.

INTRODUCTION

Indeed, high-quality channel estimation is an essential feature of reliable communication systems.

One of the major challenges of communication systems is to provide accurate channel state information (CSI) at the receiver [START_REF] Oyerinde | Review of channel estimation for wireless communication systems[END_REF]. With the estimated CSI, transmitted symbols can be recovered at the receiver. In order to do this, several channel estimation techniques to provide CSI have been developed. In general, these techniques can be categorized into three classes as illustrated in Fig. 1.2 [START_REF] Du | Wireless communication systems: From RF subsystems to 4G enabling technologies[END_REF].

Channel Estimation

Training Based Channel Estimation

Blind Channel Estimation

Semiblind Channel Estimation To achieve this, the characteristic of the channel can be used to improve the performance of its estimator.

... ... A communication channel is usually modeled by its channel impulse response (CIR), which is a vector whose elements represent the complex gains associated with each multipath component of the channel. In various communication systems, such as high-definition television (HDTV) [5,[START_REF] Fan | Accurate channel estimation based on bayesian compressive sensing for next-generation wireless broadcasting systems[END_REF],

T T D data training

mmWave system [START_REF] Marzi | Compressive channel estimation and tracking for large arrays in mm-Wave picocells[END_REF][START_REF] Ma | Design and optimization on training sequence for mmWave communications: A new approach for sparse channel estimation in massive MIMO[END_REF], wideband HF [START_REF] Ying | Turbo equalization based on compressive sensing channel estimation in wideband HF systems[END_REF][START_REF] Marques | Compressed sensing for wideband HF channel estimation[END_REF], ultra-wideband [START_REF] Zhang | A compressed sensing based ultra-wideband communication system[END_REF][START_REF] Cohen | Channel estimation in UWB channels using compressed sensing[END_REF][START_REF] Sharma | A new sparse signal-matched measurement matrix for compressive sensing in UWB communication[END_REF], massive MIMO [START_REF] Rao | Compressive sensing with prior support quality information and application to massive MIMO channel estimation with temporal correlation[END_REF] and underwater communication systems [START_REF] Panayirci | Sparse channel estimation and equalization for OFDM-based underwater cooperative systems with amplify-and-forward relaying[END_REF][START_REF] Li | Low computational complexity design over sparse channel estimator in underwater acoustic OFDM communication system[END_REF], the channels can be considered sparse channels. In other words, their impulse responses are characterized by a few significant terms that are widely separated in some domain, that is, many coefficients are close to or equal to zero. Indeed, in wireless communication systems, for example, several components of the signal arrive at the receiver with a delay due to the multipath caused by the environment, making its response sparse [START_REF] Eldar | Compressed Sensing: Theory and Applications[END_REF].

The length of a sampled sparse channel can reach hundreds of symbol intervals, although the majority of taps in the sampled channel are near zero-valued. The channel sparsity is defined as the number of non-zero taps of the channel [START_REF] Berger | Application of compressive sensing to sparse channel estimation[END_REF][START_REF] Choi | Compressed sensing for wireless communications: Useful tips and tricks[END_REF]. The sparsity can significantly reduce the effective signal space dimension. That is, the size of the possible signals set in a sparse channel can be much lower than the original (supposing non-sparse) signal space dimension.

Traditional channel estimation techniques such as least squares (LS) do not exploit the channels sparsity resulting in over-parameterization and poor performance of the sparse channel estimator [START_REF] Haykin | Adaptive filter theory[END_REF]. Furthermore, classical estimation algorithms become too complex for tackling these channels [START_REF] Carbonelli | Sparse channel estimation with zero tap detection[END_REF].

The sparsity characteristic of the signal can be used to reduce the cost and complexity of the signal estimation. For example, using compressive sensing (CS), these signals can be reconstructed from fewer measurements than the required by the Shannon-Nyquist sampling theorem [START_REF] Berger | Application of compressive sensing to sparse channel estimation[END_REF][START_REF] Candes | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] Donoho | Compressed sensing[END_REF][START_REF] Candes | An introduction to compressive sampling[END_REF][START_REF] Carmi | Compressed Sensing & Sparse Filtering[END_REF]. The great advantage of CS is that it allows you to digitize only the relevant signal information at a much lower sample rate than the Nyquist rate, so the digitized signal is already in a compressed form. Compressive sensing has been applied to sparse channel estimation [START_REF] Ma | Design and optimization on training sequence for mmWave communications: A new approach for sparse channel estimation in massive MIMO[END_REF][START_REF] Panayirci | Sparse channel estimation and equalization for OFDM-based underwater cooperative systems with amplify-and-forward relaying[END_REF][START_REF] Berger | Application of compressive sensing to sparse channel estimation[END_REF][START_REF] Carbonelli | Sparse channel estimation with zero tap detection[END_REF][START_REF] Cotter | Sparse channel estimation via matching pursuit with application to equalization[END_REF][START_REF] Huang | An improved compressed sensing reconstruction algorithm used in sparse channel estimation[END_REF][START_REF] Karabulut | Sparse channel estimation using orthogonal matching pursuit algorithm[END_REF]. The structure of sparse channels can be exploited using sparse reconstruction algorithms such as Matching Pursuit (MP) [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF], Basis Pursuit (BP) [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF] and others [START_REF] Marques | A review of sparse recovery algorithms[END_REF] leading to better estimation performance.

The channel estimation can be formulated as an optimization problem. An optimization problem can be solved by using numerical algorithms that iteratively refine their solution. Generally, 1. INTRODUCTION in channel estimation, an accurate solution should be found with a small number of iterations. In addition, these algorithms require some parameters adjustments that if they are not well chosen may decrease the algorithm performance.

In order to overcome some issues of these algorithms, model-driven neural networks (NNs) are becoming popular in communications systems [START_REF] Borgerding | AMP-inspired deep networks for sparse linear inverse problems[END_REF][START_REF] He | Deep learning-based channel estimation for beamspace mmWave massive MIMO systems[END_REF][START_REF]A model-driven deep learning network for MIMO detection[END_REF][START_REF] Gregor | Learning fast approximations of sparse coding[END_REF][START_REF] Borgerding | Onsager-corrected deep learning for sparse linear inverse problems[END_REF][START_REF] Wang | Learning deep l 0 encoders[END_REF][START_REF] Metzler | Learned D-AMP: Principled neural network based compressive image recovery[END_REF][START_REF] Sprechmann | Learning efficient sparse and low rank models[END_REF][START_REF] Yao | SURE-TISTA: A signal recovery network for compressed sensing[END_REF][START_REF] Ito | Trainable ISTA for sparse signal recovery[END_REF][START_REF]Trainable ISTA for sparse signal recovery[END_REF][START_REF] Takabe | Complex field-trainable ISTA for linear and nonlinear inverse problems[END_REF]. Some of them are based on algorithms which have performance guarantees and NNs tools, combining the best of both.

Starting with the study of compressive sensing, sparse recovery algorithms, and neural network, this thesis aims at contributing to the development of algorithms suitable for sparse channel estimation. In this work, the channel estimation is formulated as a signal recovery problem. The developed approaches are intended to be used in Software Defined Radio (SDR) applications.

However, they can be applied in other areas where the signal of interest can be considered sparse or compressible.

Thesis Contributions

This thesis is focused on sparse channel estimation. The main research contributions are:

• Study of sparse recovery algorithms (see Chapter 3) resulting in the publication of a review article in IEEE Access [START_REF] Marques | A review of sparse recovery algorithms[END_REF].

• Performance comparison between some sparse recovery algorithms that have been presented in the literature (see Section 3.4).

• Proposition of a greedy algorithm called Matching Pursuit based on Least Squares (MPLS) (see Section 5.1).

• Wideband HF channel estimation based on CS (see Section 5.2).

• Proposal of a new approach to improve Learned Iterative Shrinkage-Thresholding Algorithm (LISTA) estimation performance (see Section 5.3).

• Proposal of a new neural network to sparse signal estimation (see Section 5.4).

• Analysis of alternative shrinkage functions to be used in LISTA (see Section 5.5).

Organization of the Thesis

This report is organized into six chapters, divided as follows:

Chapter 2 is dedicated to introduce the background of this thesis. First, Software Defined Radio is addressed. Then, the concepts of sparsity and sparse signal are discussed. Finally, the basis of compressive sensing are presented and some application areas are illustrated.

An overview of sparse recovery algorithms is presented in Chapter 3. These algorithms can be classified into three categories: convex relaxation, non-convex optimization techniques and greedy algorithms. Some algorithms of each category are addressed in this chapter. Moreover, performance comparisons of them are also analyzed.

Chapter 4 discusses some neural networks proposed in the literature to deal with sparse signals estimation.

Chapter 5 presents the main contributions of this thesis. Based on the analysis made in Chapter 3, a sparse recovery algorithm called Matching Pursuit based Least Square (MPLS) is proposed.

This algorithm as well as other greedy algorithms are applied to Wideband HF channel estimation.

In addition, the study of the neural networks addressed in Chapter 4 led to the suggestion of two approaches to improve LISTA estimation performance. Furthermore, a neural network is proposed to sparse signal estimation. Finally, a performance comparison between the techniques proposed in this thesis and other sparse recovery algorithms is analyzed.

Chapter 6 concludes the work accomplished during this thesis and presents some perspectives of future research directions.

Chapter 2

Basic Concepts

This chapter introduces some concepts related to the thesis subject. Firstly, some characteristics of Software Defined Radio are addressed. Then, sparse signal and sparsity are explained. Finally, key concepts of the compressive sensing theory are presented and its applications are illustrated.

Software Defined Radio (SDR)

A radio is a device that wirelessly transmits or receives signals in the radio frequency (RF) part of the electromagnetic spectrum. It can be found in many everyday items such as cell phones, television, and vehicles. With the amount of data and ways of communication between people growing very fast, modifying radio devices efficiently to respond to today's different communication needs has become a major challenge and goal of civil and military circles.

Using traditional hardware based radio devices, a physical intervention is required to modify them limiting cross-functionality and higher production costs. In contrast, Software Defined Radio (SDR) represents a great alternative providing an efficient and comparatively inexpensive solution to this problem [START_REF] Forum | What is software defined radio?[END_REF].

The SDR Forum defines an SDR as "a radio in which some or all of the physical layer functions are software defined" [START_REF] Forum | What is software defined radio?[END_REF]. In other words, an SDR is a radio implemented with generic hardware that can be programmed to transmit and to receive a variety of waveforms. A Waveform can be defined as the set of transformations applied to information to be transmitted and the corresponding set of transformations to convert received signals back to their information content [START_REF] Collins | Software-Defined Radio for Engineers[END_REF].

This progress is due to improvements in several areas, such as embedded systems, analog to digital converters (ADC), digital transmission, digital signal processing, multi-band antennas, software architectures, and the ability to run new general purpose processors (GPP). Based on this, SDR anticipates important advantages for the development of wireless solutions in civil and military communications systems. Among the features envisioned are the interoperability between troops of different military forces and nations, the portability of waveforms, and the possibility of updating with new wireless features and capabilities without requiring new hardware, reducing logistical support and operating expenditures [START_REF] Forum | What is software defined radio?[END_REF]. SDR also allows that new products be more quickly introduced into the market using a common platform architecture and reducing development costs. In addition, SDR is viewed as the most suitable platform for the development of cognitive radios (CR).

The high-level functional model of an SDR consists of an RF front-end subsystem that performs channel selection, down-conversion to the basic band, and data routing to a processing unit based on software. In this unit, the associated digital data set is presented to several layers (e.g., link modules, network, security) to perform decoding tasks suitable for extracting the desired information. This process is inverted on the transmission side, where the input signal is encoded and modulated, appropriately for the transmission of information. This signal is then passed to the RF subsystem for insertion into the radio channel.

Due to the multiplicity of concepts related to the functional model described in the previous paragraph, several efforts have been made to standardize key elements within the SDR architecture, providing a common platform for the development of radio equipment. Supported standards can be proprietary or industry-standard, being developed through a consensus process. While the first approach brings product differentiation to manufacturers, the second strategy commoditizes the technology, enabling third party support in building the radio platform to achieve specific business objectives. One of the most typical zones for standardization is the application framework, which provides a common software operating environment in which the vendor freely provides a set of interfaces for installing, configuring, controlling, and releasing application operation on a SDR platform. Examples of application frameworks relevant to SDR systems include the Open Mobile Alliance and the Software Communications Architecture (SCA) [START_REF] Aguayo Gonzalez | Understanding the software communications architecture[END_REF].

Sparse Signals

Sparse signals are characterized by the concentration of large part of its energy in a small fraction of its duration. That is, few of their coefficients have non-zero values, and that concentrate the relevant information. These signals can be found in several domains [START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF]. For example, most of the images and the audio signals have a sparse decomposition on a base of wavelets and time-frequencies, respectively. The next paragraphs introduce sparse signals based on their vector representation.

Consider the support of a vector x is defined as the index set of its non-zero elements, that is:

supp(x) = {i : x(i) = 0} (2.1)
The sparsity of a signal x can be measured by its l 0 -norm (see (2.2)). A s-sparse signal has no more than s non-zero coefficients. On the other hand, let I(k) be the k th largest component of

x sorted by magnitude from largest to smallest, r ≥ 1, and C a constant, the coefficients x(i) of a compressible signal decrease in magnitude according to (2.3) [START_REF] Candes | Stable signal recovery from incomplete and inaccurate measurements[END_REF]. Due to their rapid decay, such signals can be well approximated by s-sparse signals, keeping just the s largest coefficients of x. Dealing with sparse signals presents several advantages such as lower computational complexity, lower processing time and less memory required during vector and/or matrix multiplication.

||x|| 0 = #supp(x) = #{i : x(i) = 0} (2.2) |x(I(k))| Ck r k = 1, ..., n (2.3)
Therefore, the performance of sparse signal processing algorithms can be improved if the sparsity characteristic of the signal is taken into account.

Compressive Sensing (CS)

Nyquist-Shannon sampling theorem establishes a condition for a sample rate that permits perfectly reconstructing a signal of finite bandwidth, i.e., the sample rate (Nyquist rate) has to be twice the bandwidth of the signal. Traditionally, signal acquisition and transmission firstly sample the signal at the Nyquist rate, then compress it. Nevertheless, it is worth to mention that in several scenarios, the Nyquist rate can be very high, resulting in too many samples, which makes it difficult to process it. In other words, it leads to many challenges related to high sampling rates for data acquisition and large amounts of data for storage and transmission.

The compressive sensing (CS) theory, also known as compressed sensing or compressive sampling, appears as an alternative approach to the traditionally signal processing. In order to reduce energy consumption and time processing, improve storage capacities and facilitate signal processing, CS performs signal sampling and compression simultaneously [START_REF] Candes | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] Donoho | Compressed sensing[END_REF][START_REF] Candes | Stable signal recovery from incomplete and inaccurate measurements[END_REF][START_REF] Candes | Near-optimal signal recovery from random projections: Universal encoding strategies?[END_REF][START_REF]Decoding by linear programming[END_REF]. Employing sparse representation, that is, the underlying assumption that the signal is sparse or compressible by some transforms (e.g., Fourier, wavelets), CS allows recover signals from fewer measurements than the Nyquist rate (sub-Nyquist sampling) reducing data acquisition costs.

Although the term "compressive sensing" has become popular in the last decades, its idea is very old. Gaspard Riche de Prony can be considered as one of the first to deal with ideas related to sparse estimation [START_REF] Verdun | Compressive sensing[END_REF]. In 1795, he was interested in recovering small number of exponential terms sampled in the presence of noise [START_REF] De Baron De Prony | Essai expérimental et analytique: Sur les lois de la dilatabilité de fluides élastique et sur celles de la force expansive de la vapeur de l'alcool, à différentes températures[END_REF]. On the other hand, works on Geology and Geophysics in the eighties showed that wideband seismic signal can be recovery by very incomplete measurements [START_REF] Levy | Reconstruction of a sparse spike train from a portion of its spectrum and application to high-resolution deconvolution[END_REF][START_REF] Walker | Autoregressive recovery of the acoustic impedance[END_REF] and one of the first paper to explicit use of l 1 -norm for signal reconstruction was written [START_REF] Santosa | Linear inversion of band-limited reflection seismograms[END_REF]. The general algorithmic principles that are used in compressive sensing were published in [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF][START_REF] Chen | Basis pursuit[END_REF][START_REF] Donoho | Uncertainty principles and ideal atomic decomposition[END_REF]. Nevertheless, the foundation of compressive sensing is related to [START_REF] Candes | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] Donoho | Compressed sensing[END_REF][START_REF] Candes | Stable signal recovery from incomplete and inaccurate measurements[END_REF][START_REF] Candes | Near-optimal signal recovery from random projections: Universal encoding strategies?[END_REF][START_REF]Decoding by linear programming[END_REF].

Basics on Compressive Sensing

Compressive sensing allows to achieve two highly targeted objectives [START_REF] Donoho | Compressed sensing[END_REF]:

• to reduce the energy for transmission and storage through the projection of the information into a lower dimensional space;

• to reduce the power consumption by reducing the sampling rate to the signal's information content rather than to its bandwidth. Fig. 2.2 illustrates the three main steps involved in compressive sensing [START_REF] Candes | An introduction to compressive sampling[END_REF][START_REF] Arjoune | Compressive sensing: Performance comparison of sparse recovery algorithms[END_REF]:

• Sparse Representation;

• CS acquisition (measurement);

• CS reconstruction (sparse recovery). In the first step (Sparse Representation), the signal is represented as a projection on a suitable basis, i.e., a linear combination of only s basis vectors, with s N. It means that a signal z with N × 1 column vector in its original representation can be represented with a basis of N × 1 vectors

Sparse Representation

{ψ i } N i=1 .
Let Ψ be the N × N basis matrix, the signal can be represented in its sparse form h by:

z = Ψh (2.4)
In the second step (CS Acquisition), the signal z is measured by sampling it according to a matrix Φ ∈ C M×N , where φ i denotes the i th column of the matrix Φ. The system model is defined by:

y = Φz + n = ΦΨh + n = Ah + n (2.5)
where y = [y 1 , y 2 , ..., y M ] T denotes the received signal, h = [h 1 , h 2 , ..., h N ] T is the sparse signal vector with N > M and n is the noise.

The third step (CS Reconstruction) deals with recovery, which is possible if the following two fundamental premises underlying CS are attended [START_REF] Donoho | Compressed sensing[END_REF]:

• Sparsity -means that the signal could be characterized by few significant terms in some domain;

• Incoherence -states that distances between sparse signals are approximately conserved as distances between their respective measurements generated by the sampling process.

The largest correlation between any two elements of Ψ and Φ is measured by the coherence between these matrices and it is defined by:

µ(Φ, Ψ) = √ N max 1≤k, j≤N < ϕ k , ψ j > (2.6)
If Φ and Ψ contain correlated elements, the coherence is large. On the contrary, the coherence is small. Compressive sensing is mainly concerned with low coherence pairs. In [START_REF] Candes | Sparsity and incoherence in compressive sampling[END_REF], considering C as a constant, the authors showed that if (2.7) holds, then with overwhelming probability one sparse recovery algorithm will recover the signal.

M ≥ Cµ 2 (Φ, Ψ)s log N (2.7)
Equation (2.7) shows that fewer measurements will be required to recover the signal if the coherence between Ψ and Φ is small [START_REF] Abo-Zahhad | Compressive sensing algorithms for signal processing applications: A survey[END_REF].

As illustrated in Fig. 2.2, the last part (sparse recovery -CS Reconstruction) recovers the sparse signal from a small set of measurements y through a specific sparse recovery algorithm [START_REF] Arjoune | Compressive sensing: Performance comparison of sparse recovery algorithms[END_REF]. This step concerns the development of efficient sparse recovery algorithms. Some of them are addressed in Chapter 3. Fig. 2.3 illustrates the relationship between the variables in a noiseless scenario. This work considers a noisy scenario and that the signal to be estimated is already in its sparse representation h. Therefore, the system is defined by:

y = Ah + n (2.8)
One of the challenges associated with the sparse signal estimation is to identify the locations of the non-zero signal components. In other words, this is finding the subspace generated by no more than s columns of the matrix A, related to the received signal y. After finding these positions, the non-zero coefficients can be calculated by applying the pseudoinversion process.

CS theory addresses two main challenges: • Design of the measurement matrix A;

y = A × h M × 1 measurements M × N N × 1 s < M < N s non-zero values
• Development of a sparse recovery algorithm for the efficient estimation of h, given only y and A.

In the first challenge, the goal is to design a measurement matrix A which assures that the main information of any s-sparse or compressible signal is in this matrix [START_REF] Abo-Zahhad | Compressive sensing algorithms for signal processing applications: A survey[END_REF]. The ideal goal is to design an appropriate measurement matrix with M ≈ s.

The measurement matrix is very important in the process of sparse signal recovering. According to [START_REF] Donoho | Compressed sensing[END_REF], if the Restricted Isometry Property (RIP) defined in (2.9) is satisfied, using some recovery algorithm, it is possible to obtain an accurate estimation of the sparse signal h, for example solving an l p -norm problem [START_REF] Wen | Stable recovery of sparse signals via l p -minimization[END_REF]. δ s ∈ (0, 1) is the RIC (Restricted Isometry Constant) value and corresponds to the smallest number that achieves (2.9). The smaller δ s , the closer any submatrix of A composed by s columns is to being orthogonal.

(

-δ s )||h|| 2 2 ≤ ||Ah|| 2 2 ≤ (1 + δ s )||h|| 2 2 1
(2.9) Table 2.1 reproduces a comparison between deterministic sensing and random sensing for the measurement matrix A presented in [START_REF] Abo-Zahhad | Compressive sensing algorithms for signal processing applications: A survey[END_REF]. The random matrices are one approach to obtain a measurement matrix A that obeys the RIP condition. Many works deal with random measurement matrices generated by identical and independent distributions (i.i.d.) such as Bernoulli, Gaussian, and random Fourier ensembles [START_REF] Candes | Near-optimal signal recovery from random projections: Universal encoding strategies?[END_REF][START_REF] Baraniuk | Compressive sensing [lecture notes[END_REF][START_REF] Chen | Condition numbers of gaussian random matrices[END_REF][START_REF] Bajwa | Toeplitz-structured compressed sensing matrices[END_REF]. However, these matrices require significant space for storage and they have excessive complexity in reconstruction [START_REF] Abo-Zahhad | Compressive sensing algorithms for signal processing applications: A survey[END_REF]. Furthermore, it is difficult to verify whether these matrices satisfy the RIP property with a small RIC value [START_REF] Abo-Zahhad | Compressive sensing algorithms for signal processing applications: A survey[END_REF].

Therefore, deterministic matrices have been studied to be used as measurement matrices. In [START_REF] Amini | Matrices with small coherence using p-ary block codes[END_REF] and [START_REF] Calderbank | Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property[END_REF], the authors propose deterministic measurement matrices based on coherence and based on RIP, respectively. Moreover, deterministic measurement matrices are constructed via algebraic curves over finite fields in [START_REF] Li | Deterministic construction of compressed sensing matrices via algebraic curves[END_REF]. Furthermore, a survey on deterministic measurement matrices for CS can be found in [START_REF] Nguyen | Deterministic sensing matrices in compressive sensing: A survey[END_REF].

Having defined the appropriate measurement matrix A, h can be estimated by the least squares (LS) solution of (2.8), i.e., solving the problem (2.10), where ε is a predefined error tolerance.

min || ĥ|| 2 sub ject to ||y -A ĥ|| 2 2 < ε (2.10)

This system is "underdetermined" (the matrix A has more columns than rows). Normally, an underdetermined system has an infinite number solutions. However, considering that the signal is sparse, the number of solutions is reduced.

Let A † be the pseudo-inverse matrix of A and AA H has an inverse matrix, according to the LS algorithm, the unique solution ĥ of the optimization problem (2.10) is given by (2.11) [START_REF] Haykin | Adaptive filter theory[END_REF].

ĥLS = A † y = A H (AA H ) -1 y (2.11) Fig. 2.
4 illustrates an example of the estimation of the sparse signal h using the LS algorithm.

It is worth noting that the least squares minimization problem leads to the lowest energy solution, however it may not return a sparse vector (see the estimate ĥLS in Fig. 2.4). Therefore, alternatives have been sought. By focusing on the sparsity constraint on the solution and solving the l 0 norm minimization described by (2.12), it is possible to obtain a sparse approximation ĥ. The Lemma 1.2 of [START_REF]Decoding by linear programming[END_REF] shows that if the matrix A obeys the RIP condition with constant δ 2s < 1, (2.12) has an unique solution and h can be reconstructed exactly from y and A. Unfortunately, an exhaustive search over all N s possible sparse combinations is required in the l 0 minimization problem, which is computationally intractable for some practical applications. Thus, although this gives the desired solution, in practice it is not feasible to solve this equation.

The excessive complexity of such a formulation can be avoided with the minimization of the l 1 problem (2.13), which can efficiently compute (2.12) under certain conditions, as demonstrated in [START_REF] Elad | A generalized uncertainty principle and sparse representation in pairs of bases[END_REF].

min || ĥ|| 1 sub ject to ||y -A ĥ|| 2 2 < ε (2.13)
One of the advantages of the l 1 norm minimization approach is that it can be solved efficiently by linear programming techniques [START_REF] Donoho | Fast solution of l 1 -norm minimization problems when the solution may be sparse[END_REF]. Moreover, in [START_REF] Donoho | Counting faces of randomly projected polytopes when the projection radically lowers dimension[END_REF], the authors state that sparse signals can be recovered through l 1 minimization if M ≈ 2s log(N).

Application of Compressive Sensing

This section overviews some application areas where CS can be suitable [START_REF] Marques | A review of sparse recovery algorithms[END_REF]. Fig.

Image and Video

Compressive Imaging Natural images can be sparsely represented in wavelet domains, so the required number of measurements in compressive imaging can be reduced using CS [START_REF] Satat | Lensless imaging with compressive ultrafast sensing[END_REF][START_REF] Dias | Block based compressive sensed thermal image reconstruction using greedy algorithms[END_REF]. One example of application is the single-pixel camera that allows reconstructing an image in a sub-Nyquist image acquisition, that is, from fewer measurements than the number of reconstructed pixels [START_REF] Duarte | Single-pixel imaging via compressive sampling[END_REF].

Medical Imaging CS can be very useful for medical imaging. For example, the magnetic resonance imaging (MRI) is a time-consuming and costly process. CS allows to decrease the number of samples, and then to reduce the time of acquisition [START_REF] Saucedo | Improved computational efficiency of locally low rank MRI reconstruction using iterative random patch adjustments[END_REF]. Similarly, bio-signals such as ECG signals are sparse in either wavelet or Fourier domain [START_REF] Pareschi | Hardwarealgorithms co-design and implementation of an analog-to-information converter for biosignals based on compressed sensing[END_REF]. CS allows to take advantage of the sparsity and reduces the required number of collected measurements [START_REF] Saucedo | Improved computational efficiency of locally low rank MRI reconstruction using iterative random patch adjustments[END_REF][START_REF] Pareschi | Hardwarealgorithms co-design and implementation of an analog-to-information converter for biosignals based on compressed sensing[END_REF][START_REF] Vasanawala | Practical parallel imaging compressed sensing MRI: Summary of two years of experience in accelerating body MRI of pediatric patients[END_REF][START_REF] Craven | Adaptive dictionary reconstruction for compressed sensing of ECG signals[END_REF]. A hardware implementation on a system on chip (SoC) platform of a solution to tackle big data transmission and privacy issues is presented in [START_REF] Djelouat | System-on-chip solution for patients biometric: A compressive sensing-based approach[END_REF].

Video Coding Due to the development and the increase of video surveillance, mobile video, and wireless camera sensor networks, wireless video broadcasting is becoming more popular and finding several real-time applications [START_REF] Pudlewski | Compressed-sensing-enabled video streaming for wireless multimedia sensor networks[END_REF][START_REF] Srinivasarao | A novel framework for compressed sensing based scalable video coding[END_REF]. In these cases, a single video stream is simultaneously transmitted to several receivers with different channel conditions [START_REF] Srinivasarao | A novel framework for compressed sensing based scalable video coding[END_REF]. In order to do this, many new video codecs have been proposed using compressive sensing [START_REF] Srinivasarao | A novel framework for compressed sensing based scalable video coding[END_REF][START_REF] Li | A new compressive video sensing framework for mobile broadcast[END_REF][START_REF] Goldstein | The STOne transform: Multi-resolution image enhancement and compressive video[END_REF][START_REF] Baraniuk | Compressive video sensing: Algorithms, architectures, and applications[END_REF].

Compressive Radar Radar imaging systems aim to determine the direction, altitude, and speed of fixed and moving objects [START_REF] Siddamal | A survey on compressive sensing[END_REF]. By solving an inverse problem using the compressive sensing theory, the received radar signal can be recovered from fewer measurements [START_REF] Siddamal | A survey on compressive sensing[END_REF]. Therefore, the cost and the complexity of the hardware of the receiver are extremely reduced [START_REF] Siddamal | A survey on compressive sensing[END_REF][START_REF] Herman | Compressed sensing radar[END_REF]. Moreover, the CS has been a novel way to deal with the Inter-Burst Translational Motion Compensation (IBTMC) to achieve the exact recovery of Inverse Synthetic Aperture Radar (ISAR) images from limited measurements [START_REF] Kang | ISAR imaging of high-speed maneuvering target using gapped stepped-frequency waveform and compressive sensing[END_REF].

Compressive Transmission Data

Wireless Sensor Networks Wireless sensor networks (WSNs) require high communication costs and energy consumption. Due to critically resource constraints as limited power supply, communication bandwidth, memory, and processing performance, CS can be used to reduce the number of bits to be transmitted or to represent the sensed data in WSNs [START_REF] Akyildiz | Wireless sensor networks: A survey[END_REF][START_REF] Razzaque | Compression in wireless sensor networks: A survey and comparative evaluation[END_REF][START_REF] Karakus | Analysis of energy efficiency of compressive sensing in wireless sensor networks[END_REF][START_REF] Hooshmand | Covariogram-based compressive sensing for environmental wireless sensor networks[END_REF].

Internet of Things The use of internet of things (IoT) devices has increased and it is estimated that it will continue to do so in the following years. This includes home automation/control devices, security cameras, mobile phones, and sensing devices [START_REF] Li | Compressed sensing via dictionary learning and approximate message passing for multimedia internet of things[END_REF]. However, the IoT devices have computation, energy, and congestion constraints. Even if they need to transmit large amounts of data, they usually have limited power and low-computation capabilities. Moreover, given the large number of devices connected, they can suffer from congestion and packet drops [START_REF] Li | Compressed sensing via dictionary learning and approximate message passing for multimedia internet of things[END_REF]. Thus, special data transmission strategies have to be developed to enable low-power and low-cost signal processing operations, and energy-efficient communications [START_REF] Li | Compressed sensing via dictionary learning and approximate message passing for multimedia internet of things[END_REF]. Multimedia data usually possesses sparse structures. Therefore, the CS theory emerges as a good strategy to reduce the amount of data that the IoT devices need to transmit with a high fidelity recovery data [START_REF] Mangia | Low-cost security of IoT sensor nodes with rakeness-based compressed sensing: Statistical and known-plaintext attacks[END_REF].

Astrophysical signals Radio receivers located in outer space suffer from strong restrictions on storage capacity, energy consumption, and transmission rate. To overcome these challenges, sampling architectures using CS provide a data acquisition technique with fewer measurements. Thus, the amount of collected data to be downloaded to Earth and the energy consumption are reduced.

The simple coding process with low computational cost provided by the CS promotes its use in real-time applications often found onboard spacecrafts. Moreover, the reconstruction of the signals will be done on Earth where there are much more computing and energy resources than onboard a satellite [START_REF] Gargouri | Compressed sensing for astrophysical signals[END_REF][START_REF] Bobin | Compressed sensing in astronomy[END_REF].

Machine Learning Machine learning algorithms perform pattern recognition (e.g., classification) on data that is too complex to model analytically to solve high-dimensional problems. However, the amount of information generated by acquisition devices is always huge and ever-growing.

It can achieve gigabytes of data or more that exceeds the processing capacity of the most sophisticated machine learning algorithms [START_REF] Yang | A machine learning paradigm based on sparse signal representation[END_REF]. To reduce the energy consumption of the applications, as in low-power wireless neural recording tasks, signals must be compressed before transmission to extend battery life. In these cases, the CS can be used and it was demonstrated its potential in neural recording applications [START_REF] Yang | A machine learning paradigm based on sparse signal representation[END_REF][START_REF] Lu | Compressed signal processing on nyquist-sampled signals[END_REF][START_REF] Sun | A deep learning framework of quantized compressed sensing for wireless neural recording[END_REF].

Communication Systems

Cognitive Radios Cognitive radios (CRs) aim to provide a solution to the inefficient usage of the frequency spectrum. Spectrum sensing techniques suffer from computational complexity, hardware cost, and high processing time [START_REF] Arjoune | Compressive sensing: Performance comparison of sparse recovery algorithms[END_REF]. Since usually only some of the available channels are occupied by the users, the signal of interest is normally sparse in the frequency domain. Hence, the CS can be used to sense a wider spectrum with reduced sampling requirements, resulting in more power efficient systems [START_REF] Sharma | Application of compressive sensing in cognitive radio communications: A survey[END_REF][START_REF] Sun | Wideband spectrum sensing for cognitive radio networks: a survey[END_REF][START_REF] Ali | Advances on spectrum sensing for cognitive radio networks: Theory and applications[END_REF][START_REF] Salahdine | A survey on compressive sensing techniques for cognitive radio network[END_REF].

Sparse Channel Estimation As said in Section 1.1, channels of several communication systems can be considered or well modelled as sparse channels. In these cases, better results can be achieved using the compressive sensing theory to estimate these channels [START_REF] Marques | Compressed sensing for wideband HF channel estimation[END_REF][START_REF] Berger | Application of compressive sensing to sparse channel estimation[END_REF][START_REF] Bajwa | Compressed channel sensing: A new approach to estimating sparse multipath channels[END_REF][START_REF] Mansoor | Massive-MIMO sparse uplink channel estimation using implicit training and compressed sensing[END_REF]. For instance, a low-complexity CS hardware implementation for channel estimation in the integrated services digital broadcasting-terrestrial (ISDB-T) system is proposed in FPGA in [START_REF] Ferdian | A low-complexity hardware implementation of compressed sensing-based channel estimation for ISDB-T system[END_REF].

Analog to Information Converter

The analog to digital converter (ADC) is based on the Nyquist sampling theorem in order to have a perfectly reconstruction of the information. That is, the signal is uniformly sampled at a rate at least twice its bandwidth. In several applications, the information of the signal is much smaller than its bandwidth. In these cases, this represents a waste of hardware and software resources to sample the whole signal. To deal with this, an analog to information converter (AIC) can use the CS theory to acquire a large bandwidth with relaxed sampling rate requirements, enabling faster, less expensive, and more energy-efficient solutions [START_REF] Tropp | Beyond nyquist: Efficient sampling of sparse bandlimited signals[END_REF][START_REF] Chen | A sub-nyquist rate sampling receiver exploiting compressive sensing[END_REF][START_REF] Pelissier | Non-uniform wavelet sampling for rf analog-to-information conversion[END_REF][START_REF] Guo | A fully passive compressive sensing SAR ADC for low-power wireless sensors[END_REF][START_REF] Zhang | Novel schemes to optimize sampling rate for compressed sensing[END_REF]. Examples of AIC are: random demodulator [START_REF] Guo | A fully passive compressive sensing SAR ADC for low-power wireless sensors[END_REF][START_REF] Laska | Theory and implementation of an analog-to-information converter using random demodulation[END_REF][START_REF] Ragheb | A prototype hardware for random demodulation based compressive analog-to-digital conversion[END_REF], modulated wideband converter [START_REF] Chen | Modulated wideband converter with non-ideal lowpass filters[END_REF] and non-uniform sampling [START_REF] Pelissier | Non-uniform wavelet sampling for rf analog-to-information conversion[END_REF][START_REF] Bellasi | VLSI design of a monolithic compressive-sensing wideband analog-to-information converter[END_REF][START_REF] Gargouri | Analog-to-information converter design for low-power acquisition of astrophysical signals[END_REF][START_REF] Trakimas | A compressed sensing analog-to-information converter with edge-triggered sar adc core[END_REF]. All these architectures have advantages and limitations. While the random demodulator AIC employs finite temporal sampling functions with infinite spectral support, the modulated wideband converter AIC has finite spectral sampling functions with infinite temporal support. Moreover, the modulated wideband converter AIC requires a large number of branches, so synchronization among the branches is also required, thus consuming more area and power. On the other hand, the non-uniform sampling AIC is sensitive to timing jitter, i.e., a sampling time with a small error can lead to a big error in the sample value for input signals that change rapidly.

Detection and Recognition Systems

Speech Recognition Dictionary of example speech tokens can be used to sparsely represent speech signals [START_REF] Gemmeke | Compressive sensing for missing data imputation in noise robust speech recognition[END_REF]. Moreover, the speech signal can have sparse representation for a suitable selection of sparse basis functions, but for the noise, it will be difficult to derive a sparse representation. Therefore, it is possible to exploit this characteristic and through the CS theory achieve a better speech recognition performance [START_REF] Gemmeke | Compressive sensing for missing data imputation in noise robust speech recognition[END_REF][START_REF] Gavrilescu | Improved automatic speech recognition system by using compressed sensing signal reconstruction based on l 0 and l 1 estimation algorithms[END_REF][START_REF] Shukla | A survey on recent advances in speech compressive sensing[END_REF].

Seismology The compressive sensing theory has an important use in data acquisition, that is, situations when it is intricate to obtain a lot of samples, for example in the case of seismic data [START_REF] Latif | An efficient undersampled high-resolution radon transform for exploration seismic data processing[END_REF].

The layers of the Earth can be estimated by measuring the reflections of a signal from different layers of the Earth. However, this requires a large data collection that is a time-consuming and expensive process. To deal with this, several works have proposed the CS for different seismic applications [START_REF] Latif | An efficient undersampled high-resolution radon transform for exploration seismic data processing[END_REF][START_REF] Cao | A review on restoration of seismic wavefields based on regularization and compressive sensing[END_REF][START_REF] Stork | The decline of conventional seismic acquisition and the rise of specialized acquisition: This is compressive sensing[END_REF].

Direction-of-Arrival Direction-of-Arrival (DOA) estimation is the process of determining which direction a signal impinging on an array has arrived from [START_REF] Hawes | Bayesian compressive sensing approaches for direction of arrival estimation with mutual coupling effects[END_REF][START_REF] Wang | Effective block sparse representation algorithm for DOA estimation with unknown mutual coupling[END_REF]. Since there are only a few non-zeros in the spatial spectrum of array signals, which represent their corresponding spatial locations, this sparsity can be applied to the DOA estimation [START_REF] Zhao | Direction-of-arrival estimation of multipath signals using independent component analysis and compressive sensing[END_REF]. Hence, the compressive sensing theory can be applied to the problem of DOA estimation by splitting the angular region into N potential DOAs, where only s N of the DOAs have an impinging signal (alternatively Ns of the angular directions have a zero-valued impinging signal present) [START_REF] Malioutov | A sparse signal reconstruction perspective for source localization with sensor arrays[END_REF][START_REF] Bilik | Expected likelihood for compressive sensingbased DOA estimation[END_REF]. These DOAs are then estimated by finding the minimum number of DOAs with a non-zero valued impinging signal that still gives an acceptable estimate of the array output [START_REF] Hawes | Bayesian compressive sensing approaches for direction of arrival estimation with mutual coupling effects[END_REF][START_REF] Shen | Underdetermined DOA estimation under the compressive sensing framework: A review[END_REF].

Chapter 3

Sparse Recovery Algorithms

This chapter discusses several sparse recovery algorithms that have been proposed in the last years.

Sparse recovery algorithms have to recover a sparse signal from an undersampled set of measurements. They are usually classified into three main categories: convex relaxation, non-convex optimization techniques, and greedy algorithms [START_REF] Carmi | Compressed Sensing & Sparse Filtering[END_REF]. Fig. 3.1 shows the algorithms that will be addressed in this chapter and their classification into these categories. In addition to the description of each of them, the following text provides an analysis and comparison of their performances. Section 3.1 presents some algorithms from the first category (convex relaxation). These algorithms result in convex optimization problems whose efficient solutions exist relying on advanced techniques, such as projected gradient methods, interior-point methods, or iterative thresholding [START_REF] Berger | Application of compressive sensing to sparse channel estimation[END_REF].

On the other hand, non-convex optimization approaches described in Section 3.2 can recovery the signal by taking into account a previous knowledge of its distribution [START_REF] Arjoune | Compressive sensing: Performance comparison of sparse recovery algorithms[END_REF]. Thanks to a posteriori probability density function, these solutions offer complete statistics of the estimate.

Nonetheless, they can be unsuitable for high-dimensional problems due to their intensive computational requirements [START_REF] Kanevsky | Kalman filtering for compressed sensing[END_REF].

The third category is composed of the greedy algorithms. They recover the signal in an iterative way, making a local optimal selection at each iteration hoping to find the global optimum solution at the end of the algorithm (see Section 3.3).

Convex Relaxation

Basis Pursuit (BP)

Basis Pursuit (BP) is a signal processing technique that decomposes the signal into an superposition of basic elements. This decomposition is optimal in the sense that it leads to the smallest l 1 norm of coefficients among all such decompositions [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF]. The BP algorithm seeks to determine a signal's representation that solves the problem:

min ||h|| 1 sub ject to y = Ah (3.1)
BP is a principle of global optimization without any specified algorithm. One of a possible algorithm to be used is the BP-simplex [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF] that is inspired by the simplex method of linear programming [START_REF] Vanderbei | Linear Programming: Foundations and Extensions[END_REF]. For the BP-simplex, first, an initial basis A(Λ) is found by selecting M linearly independent columns of A. Then, at each step, the swap which best improves the objective functions is chosen to update the current basis, that is, one term in the basis is swapped for one term that is not in the basis [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF].

In [START_REF] Huggins | Greedy basis pursuit[END_REF], the authors propose an algorithm for BP called Greedy Basis Pursuit (GBP). Unlike standard linear programming methods for BP, the GBP algorithm proceeds more like the MP algorithm, that is, it builds up the representation by iteratively selecting columns based on computational geometry [START_REF] Huggins | Greedy basis pursuit[END_REF]. Moreover, the GBP allows discarding columns that have already been selected [START_REF] Huggins | Greedy basis pursuit[END_REF].

BP De-Noising (BPDN) / Least Absolute Shrinkage and Selection Operator (LASSO)

The Basis Pursuit Denoising (BPDN) [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF] / Least Absolute Shrinkage and Selection Operator (LASSO) [START_REF] Tibshirani | Regression shrinkage and selection via the LASSO[END_REF] algorithm considers the presence of the noise n:

min ||h|| 1 sub ject to y = Ah + n (3.2)
and aims to solve the optimization problem defined by:

min( 1 2 ||y -Ah|| 2 2 + λ p ||h|| 1 ) (3.3)
where λ p > 0 is a scalar parameter [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF][START_REF] Tibshirani | Regression shrinkage and selection via the LASSO[END_REF]. The term λ p ||h|| 1 promotes sparseness of a reconstruction vector.

Its value greatly influences on the performance of the LASSO algorithm and therefore should be chosen carefully. In [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF], the authors suggest:

λ p = σ 2 log(p) (3.4)
where σ > 0 is the noise level and p is the cardinality of the dictionary [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF].

Comparing with the LS cost function, it is possible to see that (3.3) basically includes a l 1 norm penalty term. Hence, under certain conditions, the solution would achieve the minimal LS error [START_REF] Li | Estimation and tracking of rapidly time-varying broadband acoustic communication channels[END_REF]. Since ||h|| 1 is not differentiable for any zero position of h, it is not possible to obtain an analytical solution for the global minimum of (3.3).

There are several iterative techniques to find the minimum of (3.3) [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF][START_REF] Tibshirani | Regression shrinkage and selection via the LASSO[END_REF]. One of these is called "Shooting" [START_REF] Fu | Penalized regressions: The bridge versus the LASSO[END_REF] and starts by the solution:

ĥ = (A H A + I) -1 A H y (3.5)
where I is the identity matrix. Let a j be the j th column of the matrix A and B j be defined by (3.7), each j th element of ĥ is updated by: ĥ

( j) =            λ-B j a T j a j , i f B j > λ -λ-B j a T j a j , i f B j < -λ 0, i f |B j | ≤ λ (3.6) B j = -a T j y + ∑ l = j a T j a l ĥ(l) (3.7)
The original Shooting method is applied to real variables. For complex variables, an adaptation is necessary. In [START_REF] Maleki | Asymptotic analysis of complex LASSO via complex approximate message passing (CAMP)[END_REF], two schemes are presented to adapt the LASSO algorithm to estimate a complex signal h:

• r-LASSO: Let imag(.) and real(.) be the imaginary and real parts of a complex vector, respectively. It is defined by [START_REF] Maleki | Asymptotic analysis of complex LASSO via complex approximate message passing (CAMP)[END_REF]:

y R =   real(y) imag(y)   , h R =   real(h) imag(h)   , A R =   real(A) -imag(A) imag(A) real(A)   (3.8)
These definitions are used in the Shooting method in (3.5) and each j th element of ĥ is calculated by [START_REF] Maleki | Asymptotic analysis of complex LASSO via complex approximate message passing (CAMP)[END_REF]:

ĥ( j) = ĥR ( j) + √ -1 ĥR ( j + N) (3.9)
• c-LASSO: The complex l 1 -norm can be solved by some methods [START_REF] Maleki | Asymptotic analysis of complex LASSO via complex approximate message passing (CAMP)[END_REF][START_REF] Figueiredo | Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[END_REF]. It is defined by:

||h|| 1 = ∑ i |h(i)| = ∑ i real(h(i)) 2 + imag(h(i)) 2 (3.10)
In many applications, the imaginary and real components tend to be either zero or non-zero simultaneously [START_REF] Maleki | Asymptotic analysis of complex LASSO via complex approximate message passing (CAMP)[END_REF]. However, the r-LASSO does not take into account the information about any potential grouping of the real and imaginary parts [START_REF] Maleki | Asymptotic analysis of complex LASSO via complex approximate message passing (CAMP)[END_REF]. On the other hand, the c-LASSO considers this extra information [START_REF] Maleki | Asymptotic analysis of complex LASSO via complex approximate message passing (CAMP)[END_REF]. A comparison between r-LASSO and c-LASSO performed in [START_REF] Maleki | Asymptotic analysis of complex LASSO via complex approximate message passing (CAMP)[END_REF] concludes that the c-LASSO outperforms the r-LASSO since it exploits the connection between the imaginary and the real parts.

Least Angle Regression (LARS)

The Least Angle Regression (LARS) algorithm begins with ĥ = 0, the residual vector b 0 = y, and the active set Λ = / 0. This algorithm selects a new column from the matrix A at each iteration i and adds its index to the set Λ i [START_REF] Efron | Least angle regression[END_REF]. The column a j 1 that has a smaller angle with b 0 is selected at the first iteration. Then, the coefficient ĥ1 ( j 1 ) associated with the selected column a j 1 is increased [START_REF] Efron | Least angle regression[END_REF]. Next, the smallest possible step in the direction of the column a j 1 is taken until another column a j 2 has as much absolute correlation value with the current residual as the column a j 1 . The algorithm continues in a direction equiangular between the two active columns (a j 1 ,a j 2 )

until a third column a j 3 earns its way into the most correlated set [START_REF] Efron | Least angle regression[END_REF]. The algorithm stops when no remaining column has correlation with the current residual [START_REF] Efron | Least angle regression[END_REF].

Fig. 3.2 illustrates the begin of the LARS algorithm considering a two-dimensional system [START_REF] Hameed | Comparative analysis of orthogonal matching pursuit and least angle regression[END_REF].

As said before, LARS starts with ĥ0 = 0 and the residual vector b 0 = y. Let θ t (i) be the angle between the column a j i and the current residual vector b i = y -A ĥi at iteration i, the column a j 1 is selected due to its absolute correlation with the initial residual vector compared to a j 2 (θ 1 (1) < θ 1 (2)) [START_REF] Hameed | Comparative analysis of orthogonal matching pursuit and least angle regression[END_REF]. Next, the algorithm continues in the direction of a j 1 by adding the step size γ 1 . γ 1 is chosen in a way to guarantee that the columns a j 1 and a j 2 have the same absolute correlation with the current residual vector at the next iteration (θ 2 (1) = θ 2 (2)). The solution coefficient is ĥ1 ( j 1 ) = γ 1 [START_REF] Hameed | Comparative analysis of orthogonal matching pursuit and least angle regression[END_REF]. The column a j 2 is added to the set Λ at the second iteration, and the LARS continues in a equiangular direction with a j 1 and a j 2 . Then, the step size γ 2 that leads to the vector y is added [START_REF] Hameed | Comparative analysis of orthogonal matching pursuit and least angle regression[END_REF]. Finally, the solution coefficients are equal to: ĥ2

( j 1 ) = γ 1 + γ 2 d 2 ( j 1 )
and ĥ2 ( j 2 ) = γ 2 d 2 ( j 2 ), where d 2 is the updated direction at the second iteration that is equiangular with the active columns (a j 1 , a j 2 ). The estimated vector ĥ is updated by multiplying the step size γ with the updated direction d [START_REF] Hameed | Comparative analysis of orthogonal matching pursuit and least angle regression[END_REF]. The algorithm continues until the residual be zero.

a j 2 a j 2 a j 1 y γ 1 γ 2 θ 1 (2) θ 1 (1) θ 2 (2) θ 2 (1) ĥ1 (j 1 ) = γ 1 ĥ1 (j 2 ) = 0 ĥ2 (j 1 ) = γ 1 +γ 2 d 2 (j 1 ) ĥ2 (j 2 ) = γ 2 d 2 (j 2 )
Figure 3.2 -LARS approximates the vector y by using a j 1 and a j 2 .

A modified LARS called "homotopy algorithm" was proposed by Donoho and Tsaig to find a sparse solution of an underdetermined linear system [START_REF] Donoho | Fast solution of l 1 -norm minimization problems when the solution may be sparse[END_REF].

These steps can summarize the LARS algorithm [START_REF] Hameed | Comparative analysis of orthogonal matching pursuit and least angle regression[END_REF]:

• Step 1: Initialize the residual vector b 0 = y, the active set Λ = / 0, ĥ0 = 0 and the iteration counter i = 1.

• Step 2: Calculate the correlation vector:

c i = A T b i-1 .
• Step 3: Find the maximum absolute value in the correlation vector:

λ i = ||c i || ∞ .
• Step 4: Stop the algorithm if λ ≈ 0. If not, go to Step 5.

• Step 5: Find the active set:

Λ = { j : |c i ( j)| = λ i }.
• Step 6: Solve the following least square problem to find active entries of the updated direc-

tion: A T (Λ)A(Λ)d i (Λ) = sign(c i (Λ)).
• Step 7: Set the inactive entries of the updated direction to zero:

d i (Λ C ) = 0.
• Step 8: Calculate the step size γ i by:

γ i = min j∈Λ c λ i -c i ( j) 1 -a T j A(Λ)d i (Λ) , λ i + c i ( j) 1 + a T j A(Λ)d i (Λ) • Step 9: Calculate ĥi = ĥi-1 + γ i d i .
• Step 10: Update b i = y -A ĥi .

• Step 11: Stop the algorithm if ||b i || 2 < ε. Otherwise, set i = i + 1 and return to Step 2.

The Dantzig Selector (DS)

The Dantzig Selector (DS) is a solution to l 1 minimization problem [START_REF] Candes | The dantzig selector: statistical estimation when p is much larger than n[END_REF]:

min || ĥ|| 1 sub jet to ||A T b|| ∞ ≤ 1 + δ 1 λ N σ (3.11)
where b = y-A ĥ is the residual vector, σ is the standard deviation of the Additive White Gaussian Noise in (2.8), λ N > 0 and all the columns of A have norm less than

√ 1 + δ 1 . ||A T b|| ∞ is defined by: ||A T b|| ∞ = sup 1≤i≤N |(A T b) i | (3.12)
For an orthogonal matrix A, the Dantzig Selector is the l 1 -minimizer subject to the constraint

||A T y -ĥ|| ∞ ≤ λ N σ
, and the i th element of ĥ is calculated by: ĥ

(i) = max(|(A T y) i | -λ N σ, 0)sgn((A T y) i ) (3.13)

Iterative Soft Thresholding (ISTA)

In [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF], the authors demonstrate that soft thresholding can be used to minimize equations of the form:

1 2 Ah -y 2 2 + λ h 1 (3.14)
The solution is given by the limit of the sequence, where each iteration is defined by [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF]:

ĥi = η st ĥi-1 + βA T b i-1 ; λ , b i = y -A ĥi (3.15)
where ĥ0 = 0, β is a stepsize, and η st (.; λ) is the soft thresholding function defined by (3.16) applied to each element of the vector.

η st (x; λ) =          x -λ, i f x > λ 0, i f |x| λ x + λ, i f x < -λ (3.16)
Although ISTA is guaranteed to converge [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF], it converges slowly. Therefore, several modifications have been proposed to speed it up such as the "fast ISTA" (FISTA) [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm with application to wavelet-based image deblurring[END_REF] and the neural network LISTA [START_REF] Gregor | Learning fast approximations of sparse coding[END_REF] (see Section 4.2.1).

Approximate Message Passing (AMP)

The Approximate Message Passing (AMP) algorithm is described in [START_REF] Maleki | Approximate message passing algorithms for compressed sensing[END_REF][START_REF] Donoho | Message passing algorithms for compressed sensing[END_REF]. This algorithm starts by ĥ0 = 0 and b 0 = y. Then, in each iteration i, it updates these vectors by:

ĥi = η i-1 ( ĥi-1 + A T b i-1 ) (3.17) b i = y -A ĥi + 1 δ b i-1 η i-1 (A T b i-1 + ĥi-1 ) (3.18)
where δ = M/N, η i (.) is the thresholding function, x = ∑ N i=1 x(i)/N for x = (x(1), ..., x(N))

and η i (s) = ∂ ∂s η i (s). The term 1 δ b i-1 η i (A T b i-1 + ĥi-1
) is from theory of belief propagation in graphical model [START_REF] Maleki | Approximate message passing algorithms for compressed sensing[END_REF].

The thresholding function η i (.) depends on iteration and problem setting. In [START_REF] Donoho | Message passing algorithms for compressed sensing[END_REF], the authors consider the threshold control parameter λ and η i (.) = η(.; λσ i ) defined by:

η(x; λσ i ) =          (x -λσ i ), i f x ≥ λσ i (x + λσ i ), i f x ≤ -λσ i 0, otherwise (3.19)
where σ i is the mean square error of the current estimate solution ĥi at iteration i.

AMP outperforms ISTA in convergence speed, but it does not work well unless the matrix A has independent and identically distributed (i.i.d.) Gaussian entries (N (0, M -1 )) [START_REF] Yao | SURE-TISTA: A signal recovery network for compressed sensing[END_REF]. In order to overcome this restriction, the Orthogonal Approximate Message Passing (OAMP) was proposed in [START_REF] Ma | Orthogonal AMP[END_REF].

Gradient Descent with Sparsification (GraDeS)

This algorithm was proposed in [START_REF] Garg | Gradient descent with sparsification: An iterative algorithm for sparse recovery with restricted isometry property[END_REF]. It considers a measurement matrix A which satisfies the RIP with an isometric constant δ 2s < 1/3. This algorithm finds a sparse solution for the l 1 minimization problem in an iterative way.

First, the algorithm initializes the signal estimation ĥ0 = 0. Then, in each iteration i, it estimates the signal by:

ĥi = H s ĥi-1 + 1 γ A H (y -A ĥi-1 ) (3.20)
where γ > 1 and the operator H s () sets all components to zero except the s largest magnitude components.

Non-Convex Optimization Techniques

Bayesian Compressive Sensing (BCS)

Let σ 2 be the noise variance, the sparse Bayesian learning (SBL) assumes the Gaussian likelihood model [START_REF] Wipf | Sparse bayesian learning for basis selection[END_REF]:

p(y|h; σ 2 ) = (2πσ 2 ) -M/2 exp -1 2σ 2 ||y -Ah|| 2 (3.21)
In a Bayesian formulation, the formalization that h is sparse is made by placing a sparsenesspromoting prior on h [START_REF] Ji | Bayesian compressive sensing[END_REF]. The Laplace density function is a widely used sparseness prior [START_REF] Figueiredo | Adaptive sparseness using jeffreys prior[END_REF][START_REF] Bernardo | Bayesian theory[END_REF]:

p(h|λ) = λ 2 N exp -λ N ∑ i=1 |h i | (3.22)
and henceforth the subscript s on h is dropped, recognizing that the interest is in a sparse solution for the weights [START_REF] Ji | Bayesian compressive sensing[END_REF]. Thus, the solution of (2.8) corresponds to a maximum a posteriori (MAP) estimate for using the prior in (3.22) [START_REF] Tibshirani | Regression shrinkage and selection via the LASSO[END_REF][START_REF] Figueiredo | Adaptive sparseness using jeffreys prior[END_REF].

According to the Bayesian probability theory, we consider that a class of prior probability distributions p(θ) is conjugate to a class of likelihood functions p(x|θ) if the resulting posterior distributions p(θ|x) are in the same family as p(θ) [START_REF] Ji | Bayesian compressive sensing[END_REF]. Since the Laplace prior is not conjugate to the Gaussian likelihood, the relevance vector machine (RVM) is used.

Assuming the hyperparameters α and α 0 are known, a multivariate Gaussian distribution with mean and covariance given by (3.23) and (3.24) can express the posterior for h [START_REF] Ji | Bayesian compressive sensing[END_REF].

µ = α 0 ΣA T y (3.23) Σ = (α 0 A T A + D) -1 (3.24)
where D = diag(α 1 , α 2 , ...α N ). Therefore, the search for the hyperparameters α and α 0 can be seen as a learning problem in the context of the RVM. A type-II maximum likelihood (ML) procedure can be used to estimate these hyperparameters from the data [START_REF] Tipping | Sparse bayesian learning and the relevance vector machine[END_REF].

The logarithm of the marginal likelihood for α and α 0 , noted L(α, α 0 ), is given by [START_REF] Ji | Bayesian compressive sensing[END_REF]:

log p(y|α, α 0 ) = log p(y|h, α 0 )p(h|α)dh = - 1 2 M log 2π + log |C| + y T C -1 y (3.25)
with C = σ 2 I + AD -1 A T . The maximization of (3.25) can be obtained with a type-II ML approx-imation that uses the point estimates for α and α 0 . This can be achieved through the Expectation-Maximization (EM) algorithm [START_REF] Ji | Bayesian compressive sensing[END_REF][START_REF] Tipping | Sparse bayesian learning and the relevance vector machine[END_REF], to yield:

α new i = γ i µ 2 i (3.26)
where µ i is the i th posterior mean weight from (3.23) and

γ i = 1 -α i Σ ii with Σ ii the i th diagonal element of (3.24).

Focal Underdetermined System Solution (FOCUSS)

The Focal Underdetermined System Solution (FOCUSS) was proposed in [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FO-CUSS: a re-weighted minimum norm algorithm[END_REF] to solve (2.8).

First, a low-resolution initial estimate of the real signal is made. Then, the iteration process refines the initial estimate to the final localized energy solution [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FO-CUSS: a re-weighted minimum norm algorithm[END_REF]. The FOCUSS iterations are based on a weighted minimum norm solution defined as the solution minimizing a weighted norm

||W -1 h|| 2 .
It is given by [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FO-CUSS: a re-weighted minimum norm algorithm[END_REF]:

ĥ = W(AW) † y (3.27)
where the definition of a weighted minimum norm solution is to find h = Wq where q : min||q|| 2 , subject to AWq = y. The cost objective simply becomes

W † h = ∑ N i=1,w(i) =0 h(i) w(i)
2 when W is diagonal, where w i are the diagonal entries of W [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FO-CUSS: a re-weighted minimum norm algorithm[END_REF].

The basis of the basic FOCUSS algorithm lies the Affine Scaling Transformation (AST):

q = Ĥ † k-1 ĥ (3.28)
where Ĥ † k-1 = diag( ĥk-1 ) [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FO-CUSS: a re-weighted minimum norm algorithm[END_REF]. Let W p k be the a posteriori weight in each iteration, the AST is used in the basic FOCUSS algorithm to construct the weighted minimum norm constraint (3.29) by setting W p k = Ĥk-1 [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FO-CUSS: a re-weighted minimum norm algorithm[END_REF].

||W T h|| 2 2 = ||q|| 2 2 = n ∑ i=1,w i =0 h(i) w(i) 2 (3.29)
Let ĥ0 = 0, the steps of the algorithm are:

Step 1:

W p k = (diag( ĥk-1 )) (3.30)
Step 2:

q k = (AW p k ) † y (3.31)
Step 3:

ĥk = W p k q k (3.32)
The algorithm continues until a minimal set of the columns of A that describe y is obtained [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FO-CUSS: a re-weighted minimum norm algorithm[END_REF].

By introducing two parameters, the authors extend the basic FOCUSS into a class of recursively constrained optimization algorithms in [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FO-CUSS: a re-weighted minimum norm algorithm[END_REF]. In the first extension, ĥk-1 is raised to some power l [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FO-CUSS: a re-weighted minimum norm algorithm[END_REF]. While in the second extension an additional weight matrix W a k which is independent of the a posteriori constraints is used [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FO-CUSS: a re-weighted minimum norm algorithm[END_REF]. The follow steps describe the algorithm:

Step 1:

W p k = (diag( ĥl k-1 )), l ∈ N + (3.33)
Step 2:

q k = (AW a k W p k ) † y (3.34)
Step 3:

ĥk = W a k W p k q k (3.35)
It can be assumed that W a k is constant for all iterations. According to [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FO-CUSS: a re-weighted minimum norm algorithm[END_REF], l > 0.5 when h(i) > 0 is imposed.

Iterative Reweighted Least Squares (IRLS)

The Iterative Reweighted Least Squares (IRLS) algorithm is used for solving (3.36) through a weigthed l 2 norm given by (3.37), where the weights are computated from the previous iterate

h n-1 , so w(i) = |h n-1 (i)| p-2 [151]. min h ||h|| p p sub ject to Ah = y (3.36) min h N ∑ i=1 w(i)h 2 (i) sub ject to Ah = y (3.37)
Let Q n be the diagonal matrix with entries 1/w(i) = |h n-1 (i)| 2-p , the solution of (3.37) can be given by:

h n = Q n A T (AQ n A T ) -1 y (3.38)
To deal with the case 0 ≤ p ≤ 1, where w(i) will be undefined for h n-1 (i) = 0, the authors in [START_REF] Chartrand | Iteratively reweighted algorithms for compressive sensing[END_REF] regularize the optimization problem by incorporating a small ε > 0:

w(i) = ((h n-1 (i)) 2 + ε) p/2-1 (3.39)

Greedy Algorithms

Several greedy algorithms follow the steps showed in Fig. 3.3 [START_REF] Marques | A review of sparse recovery algorithms[END_REF]. There are some differences in the choice of the quantity of the column in each iteration, that is, the way to choose the indices j to compose the set J i . For instance, the MP and the OMP algorithms only choose one column in each iteration. In contrast, the StOMP algorithm chooses all columns whose the projection value is bigger than the threshold value t S . The calculation of the residual vector b i and the estimation of the non-zero values of ĥ in each iteration are other differences between the algorithms. For example, the SP algorithm estimates ĥ only at the end of the algorithm as it is explained in the subsections below.

Table 3.1 summarizes the inputs, the calculation of the residual vector b i and the signal estimate components ĥi in each iteration [START_REF] Marques | A review of sparse recovery algorithms[END_REF]. In the next subsections, the greedy algorithms presented in Fig. 3.1 are explained.

Table 3.1 -Main parameters and calculations of Greedy Algorithms.

Algorithm Inputs j b i ĥi MP A, y max j ||c( j)|| b i-1 - (a l i H b i-1 )a l i ||a l i || 2 2 (a l i H b i-1 )
||a l i || 2 2 OMP A, y max j ||c( j)|| y -A(Λ i ) ĥi A(Λ i ) † y SP A, y, s s biggest ||c( j)|| y -A(Λ i )A † (Λ i )y - StOMP A, y, T , t S j : ||c( j)|| > t S y -A(Λ i ) ĥi A(Λ i ) † y CoSaMP A, y, s 2s biggest ||c( j)|| y -A(Λ i ) ĥi supp s (A(Λ i ) † y) ROMP A, y, s s biggest ||c( j)|| y -A(Λ i ) ĥi A(Λ i ) † y GOMP A, y, Q, s Q biggest ||c( j)|| y -A(Λ i ) ĥi A(Λ i ) † y GOAMP A, y, Q Q biggest ||c( j)|| y -A(Λ i ) ĥi A(Λ i ) † y GP A, y max j ||c( j)|| b i-1 -a i A(Λ i )d i ĥi-1 + a i d i Start Parameters Initialization Projection c = A H b i-1

Subset Selection j

Support Merges

Λ i = Λ i-1 ∪ J i

Matching Pursuit (MP)

The Matching Pursuit (MP) algorithm is proposed in [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF]. Let ĥ0 = 0, each iteration i of the MP algorithm consists in finding the column a k i ∈ A which is best aligned with the residual vector b i-1 (b 0 = y) according to (3.40) [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF].

k i = arg max l |a l H b i-1 |, l = 1, 2, ...., N (3.40)
The index set Λ i stores the indices of the best aligned columns after i iterations. Let D i be the matrix formed by the columns a k i chosen until iteration i, the next step is:

• Λ i = Λ i-1 ∪ k i and D i = [D i-1 , a k i ], if k i / ∈ Λ i-1 ; • Λ i = Λ i-1 and D i = D i-1 , , if k i ∈ Λ i-1 .
Then, a new residual vector is computed as (3.41) by removing the projection of b i-1 along this direction, and the estimated coefficient is calculated by (3.42).

b i = b i-1 -P a k i b i-1 = b i-1 - (a k i H b i-1 )a k i ||a k i || 2 2 (3.41) ĥi (k i ) = ĥi-1 (k i ) + (a k i H b i-1 ) ||a k i || 2 2 (3.42)
The stop criterion of the algorithm can be, for example, ||b i || ≤ ε. The signal estimate corresponds to the projections of the best columns of the matrix A

Orthogonal Matching Pursuit (OMP)

The Orthogonal Matching Pursuit (OMP) algorithm is an improvement of the MP [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF]. It can be stated as follows:

• Step 1: Initialize b 0 = y, Λ i = /
0, and i = 1.

• Step 2: Find l that solves the maximization problem max

l ||P a l b i-1 || 2 = max l a l H b i-1 ||a l || 2 2 and up- date Λ i = Λ i-1 ∪ {l}. • Step 3: Calculate ĥi = A † (Λ i )y and update b i = y -A(Λ i ) ĥi .
• Step 4: Stop the algorithm if the stopping condition is achieved (e.g. ||b i || ≤ ε). Otherwise, set i = i + 1 and return to Step 2.

In the OMP, the residual vector b i is always orthogonal to the columns that have already been selected. Therefore, there will be no columns selected twice and the set of selected columns is increased through the iterations.

Due to the OMP selects only one column in each iteration, it is very sensitive to the selection of the index [START_REF] Kwon | Multipath matching pursuit[END_REF]. Alternatively, various approaches investigating multiple columns chosen in each iteration have been proposed such as the SP, the StOMP, the CoSaMP, the ROMP, the GOMP, the GOAMP, the MMP, and the GP algorithms. They are presented in the next sections.

Subspace Pursuit (SP)

At each stage, in order to refine an initially chosen estimate for the subspace, the Subspace Pursuit (SP) algorithm tests subsets of s columns in a group [START_REF] Dai | Subspace pursuit for compressive sensing signal reconstruction[END_REF]. That is, maintaining s columns of A, the algorithm executes a simple test in the spanned list of space, and after refines the list by discarding the unreliable candidates, retaining reliable ones while adding the same number of new candidates [START_REF] Dai | Subspace pursuit for compressive sensing signal reconstruction[END_REF]. Basically, the steps of the SP are:

• Step 1: Initialize the support set Λ 0 with the s indices corresponding to the largest magnitude entries in the vector A H y, the residual vector b 0 = y -A(Λ 0 )A(Λ 0 ) † y and the iteration counter i = 1.

• Step 2: Λi = Λ i-1 ∪ J i , where J i is the set of the s indices corresponding to the largest magnitude entries in the vector

c i = A H b i-1 . • Step 3: Calculate x i = A † ( Λi )y.
• Step 4: Update Λ i = {s indices corresponding to the largest magnitude elements of x i }.

• Step 5: Update b i = y -A(Λ i )A † (Λ i )y.
• Step 6: Stop the algorithm if the stopping condition is achieved. Otherwise, set i = i + 1 and return to Step 2.

After T iterations, the signal estimated is given by ĥ = A † (Λ T )y.

When the signal is very sparse, the SP algorithm has computational complexity upper-bounded by O(sMN) (s ≤ const.

√ N), that is, lower computational complexity than the OMP algorithm [START_REF] Dai | Subspace pursuit for compressive sensing signal reconstruction[END_REF].

However, when the non-zero components of the sparse signal decay slowly, the computational complexity of the SP can be further reduced to O(MNlogs) [START_REF] Dai | Subspace pursuit for compressive sensing signal reconstruction[END_REF].

Stagewise Orthogonal Matching Pursuit (StOMP)

The Stagewise Orthogonal Matching Pursuit (StOMP) [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF] algorithm is inspired by the OMP.

Different from the OMP algorithm, the StOMP algorithm selects multiple columns at each iteration. That is, according to a threshold, the StOMP algorithm selects the subspaces composed of the columns with the highest coherence between the remaining columns and the residual vector [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF].

The number of iterations is fixed.

The input parameters are: the number of iterations T to perform, the threshold value t S , the received signal y, and the measurement matrix A. The StOMP algorithm can be stated as follows:

• Step 1: Initialize the residual vector b 0 = y, Λ 0 = / 0, and i = 1.

• Step 2: Find a l that ||P a l b i-1 || > t S , that is, max l a l H b i-1 ||a l || 2 > t S
and add the a l columns to the set of selected columns. Update

Λ i = Λ i-1 ∪ {l}. • Step 3: Let ĥi = A(Λ i ) † y. Update b i = y -A(Λ i ) ĥi .
• Step 4: If the stopping condition is achieved (i = N it = T ), stop the algorithm. Otherwise, set i = i + 1 and return to Step 2.

Compressive Sampling Matching Pursuit (CoSaMP)

The Compressive Sampling Matching Pursuit (CoSaMP) algorithm is presented in [START_REF] Needell | CoSaMP: Iterative signal recovery from incomplete and inaccurate samples[END_REF] to mitigate the unstability of the OMP algorithm. Similarly to the OMP, it starts by initializing a residual vector as b 0 = y, the support set as Λ 0 = / 0, the iteration counter as i = 1, and additionally sets ĥ0 = 0. The CoSaMP performs these steps [START_REF] Needell | CoSaMP: Iterative signal recovery from incomplete and inaccurate samples[END_REF]:

• Step 1 -Identification: a proxy of the residual vector from the current samples is formed and the largest components of the proxy

c i = |A H b i-1 | are located.
The first 2s entries of c i with largest absolute values are selected, and the indices selected compose J i .

• Step 2 -Support merger: the set of newly identified components is united with the set of components that appears in the current approximation. Λ i = J i ∪supp( ĥi-1 ) is defined as the augmentation of the support of the previous estimate ĥi-1 with the 2s indices corresponding to the entries of c i with largest absolute values.

• Step 3 -Estimation: a least squares problem to approximate the target signal on the merged set of components is solved. xi = A(Λ i ) † y.

• Step 4 -Pruning: a new approximation by retaining only the largest entries in this least squares signal approximation is produced. ĥi is composed of the first s entries of xi with largest absolute values.

• Step 5 -Sample update: update b i = y -A(Λ i ) ĥi .

Regularized OMP (ROMP)

The Regularized OMP (ROMP) algorithm was proposed in [START_REF] Needell | Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[END_REF]. Firstly, the ROMP algorithm initializes Λ 0 = / 0 and the residual vector b 0 = y. Then, during each iteration i, the ROMP performs these three steps:

• Step 1 -Identification: Λi = {s biggest indices in magnitude of the projection vector c i = A H b i-1 }.
• Step 2 -Regularization: Among all subsets J i ⊂ Λi with comparable coordinates |c(l)| ≤ 2|c( j)| for all l, j ∈ J i , choose J i with the maximal energy ||c(J i )|| 2 .

• Step 3 -Updating: Add the set J i to the index set:

Λ i = Λ i ∪ J i . Calculate ĥi = A(Λ i ) † y and update the residual vector b i = y -A(Λ i ) ĥi .
The regularization step can be done in linear time. The running time of the ROMP is comparable to that of the OMP in theory, but it is often better than the OMP in practice [START_REF] Needell | Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[END_REF].

Generalized Orthogonal Matching Pursuit (GOMP)

The Generalized Orthogonal Matching Pursuit (GOMP) algorithm is a direct extension of the OMP algorithm [START_REF] Wang | Generalized orthogonal matching pursuit[END_REF]. The GOMP selects Q ≥ 1 largest correlation columns of the matrix A with the residual vector b.

When Q = 1, the GOMP becomes the OMP. Moreover, Q ≤ s and Q ≤ √ M.
The steps of the GOMP are:

• Step 1: Initialize the residual vector b 0 = y, Λ 0 = / 0 and i = 1.

• Step 2: Find the Q biggest a l 1 , .., a l Q columns that solves the maximization problem

max k ||P a l k b i-1 || 2 = max k a l k H b i-1 ||a l k || 2 2
and add the a l i columns to the set of selected columns.

Update Λ i = Λ i-1 ∪ {l 1 , ..., l Q }. • Step 3: Calculate ĥi = A(Λ i ) † y. Update b i = y -A(Λ i ) ĥi . • Step 4: Stop the algorithm if the stopping condition is achieved (N it = min(s, M/Q) or ||b i || 2 ≤ ε). Otherwise, set i = i + 1 and return to Step 2.
The complexity of the GOMP algorithm is approximately

2N it MN + (2Q 2 + Q)N 2 it M [158].

Generalized Orthogonal Adaptive Matching Pursuit (GOAMP)

The Generalized Orthogonal Adaptive Matching Pursuit (GOAMP) algorithm considers that the signal's sparsity is not known, so it adapts the variable Q of the GOMP algorithm during the iterations [START_REF] Sun | Compressed sensing data reconstruction using adaptive generalized orthogonal matching pursuit algorithm[END_REF]. Basically, the GOAMP inserts a new step after the update of the residual vector:

• Step 1: Initialize the residual vector b 0 = y, Λ 0 = / 0 and i = 1.

• Step 2: Find the Q biggest a l 1 , .., a l Q columns that solve the maximization problem

max k ||P a l k b i-1 || 2 = max k a l k H b i-1 ||a l k || 2 2
and add the a l i columns to the set of selected columns.

Update Λ i = Λ i-1 ∪ {l 1 , ..., l Q }. • Step 3: Calculate ĥi = A(Λ i ) † y. Update b i = y -A(Λ i ) ĥi . • Step 4: If ||b i-1 -b i || 2 2 /||b i-1 || 2 2 < ε 2 , Q = f (Q).
Otherwise, go to Step 5.

• where f (Q) is a function that increases the value of Q. According to [START_REF] Sun | Compressed sensing data reconstruction using adaptive generalized orthogonal matching pursuit algorithm[END_REF], ε 2 is about 0.7 -0.9.

Gradient Pursuit (GP)

The Gradient Pursuit (GP) algorithms were proposed in [START_REF] Blumensath | Gradient pursuits[END_REF] as variations of the MP algorithm.

In the GP, at iteration i, the signal estimate ĥi is:

ĥi = ĥi+1 + γ i d i (3.43)
where d i is the update direction and γ i is the optimal step size defined by:

γ i = < b i-1 , A(Λ i )d i > ||A(Λ i )d i || (3.44)
In the MP and the OMP algorithms, the update direction is taken to be in the direction of the best aligned column of the matrix A. In the OMP, once added, the column will not be selected again as the process of orthogonalisation ensures that all future residuals will remain orthogonal to all currently selected columns. However, in the MP and the GP the orthogonality is not ensured.

Hence, it is possible select again the same column.

Each iteration i consists in finding the column a l i ∈ A which is best aligned with the signal vector residual b i-1 . The GP algorithms perform the follow steps:

• Step 1: Initialize b 0 = y, Λ 0 = / 0 and i = 1.
• Step 2: Find l i that solves the maximization problem max

l i ||P a l i b i-1 || 2 = max l i a l i H b i-1 ||a l i || 2 2
. Update

Λ i = Λ i-1 ∪ {l i }. • Step 3: Update the direction d i . Calculate γ i = <b i-1 ,A(Λ i )d i > ||A(Λ i )d i || and ĥi = ĥi-1 + γ i d i . Update b i = b i-1 -γ i A(Λ i )d i .
• Step 4: Stop the algorithm, if the stopping condition is achieved. Otherwise, set i = i + 1 and return to Step 2.

There are three different methods for calculating the update direction d i [START_REF] Blumensath | Gradient pursuits[END_REF][START_REF] Pope | Compressive sensing: a summary of reconstruction algorithms[END_REF]:

• Gradient Pursuit: uses the direction that minimizes ||y -A ĥi-1 || 2 , that is:

d i = A T (Λ i ) y -A(Λ i ) ĥi-1 (Λ i ) (3.45)
• Conjugate Gradient Pursuit: it is a directional optimization algorithm that is guaranteed to solve quadratic optimization problems in as many steps as the dimension of the problem [START_REF] Golub | Matrix computations[END_REF]. Let φ(h) = 1 2 h T Ghf T h be the cost function to be minimized, this method chooses d i that is G-conjugate to all the previous directions, that is:

d i Gd k = 0, ∀k < i (3.46)
In this case, G = A T (Λ i )A(Λ i ). Let D i be the matrix whose columns are the update directions for the first i iterations and let g i be the gradient of the the cost function in iteration i, the new update direction d i in iteration i is given by [START_REF] Golub | Matrix computations[END_REF]:

d i = g i + D i-1 f (3.47) where f = -D T i-1 GD i-1 -1 D T i-1 Gg i-1 .
The OMP uses a full conjugate gradient solver at every iteration. Instead, in this method, only a directional update step occurs for each new added element.

• Approximate Conjugate Gradient Pursuit: the new direction is conjugate to the previous direction, but this can be extended to a larger number of directions:

d i = g i + d i-1 f (3.48)
The G-conjugacy implies that:

(Gd i-1 ) , (g i + bd i-1 ) = 0 (3.49) f = - (A(Λ i )d i-1 ) , (A(Λ i )g i ) A(Λ i )d i-1 2 2
(3.50)

Multipath Matching Pursuit (MMP)

With the help of the greedy strategy, the Multipath Matching Pursuit (MMP) algorithm executes the tree search [START_REF] Kwon | Multipath matching pursuit[END_REF]. First, the MMP algorithm searches multiple promising columns of the matrix A candidates and then it chooses one minimizing the residual in the final moment. The MMP algorithm can not be represented by Fig. 3.3. Let L be the number of child paths of each candidate, f k i be the k th candidate in the i th iteration, F i = { f 1 i , ..., f u i } be the set of candidates in the i th iteration and |F i | be the number of elements of F i , Ω k is the set of all possible combinations of k columns in A, for example, if Ω = {1, 2, 3} and k = 2, then Ω k = {{1, 2}, {1, 3}, {2, 3}} [START_REF] Kwon | Multipath matching pursuit[END_REF]. Fig. 3.4 shows a comparison from an hypothetical choice of columns in the first three iterations of the OMP and the MMP algorithms [START_REF] Kwon | Multipath matching pursuit[END_REF]. In this figure, the OMP selects the column with index 2 in the first iteration, then the index 1 in the next iteration and in the third iteration, it selects the index 4. On the other hand, the MMP algorithm selects the index 2 and 4 in the first iteration, after for each index selected, the algorithm will select others L = 2 index in each iteration. Then, in the second iteration, it selects the index 1 and 5 for the index 2 and for the index 4, but it is not necessary to select the same index as can be noted in the third iteration where the MMP selects the index 4 and 5 for the {2, 1} composing f 1 3 = {2, 1, 4} and f 2 3 = {2, 1, 5}, and the index 2 and 3 for the {4, 1} composing f 1 3 = {2, 1, 4} and f 5 3 = {4, 1, 3}. Moreover, it can be noticed that although the number of candidates increases as an iteration goes on (each candidate brings forth multiple children), the increase is actually moderate since many candidates are overlapping in the middle of search as the case of f 1 3 , f 2 3 and f 3 3 in Fig. 3.4 [START_REF] Kwon | Multipath matching pursuit[END_REF]. The residual vector of the k th candidate in the i th iteration is b k i = y -A( f k i ) ĥk i , where A( f k i ) is the matrix A using only the columns indexed by f k i . Given the measurement matrix A, the received signal y, the signal's sparsity s and the parameter L, the MMP follows the steps bellow:

• Step 1: Initialize b 0 = y, F 0 = / 0 and i = 1. • Step 2: Set F i = / 0, u = 0 and k = 1. Ø {2} {2, 1} {2, 1, 4} F 1 F 2 F 3 (a) Ø f 1 1 ={2} f 2 1 ={4} f 1 2 ={2, 1} f 2 2 ={2, 5} f 3 2 ={4, 1} f 4 2 ={4, 5} f 1 3 ={2, 1, 4} f 2 3 ={2, 1, 5} f 3 3 ={2, 5, 4} f 4 3 ={4, 5, 3} f 5 3 ={4, 1, 3} F 1 F 2 F 3 (b)
• Step 4: Set f temp = f k i-1 ∪ {π j }
, where π j is the j th element of the set π.

• Step 5: If f temp / ∈ F i then u = u + 1, f u i = f temp , F i = F i ∪ { f u i }, update ĥu i = A † ( f u i )y and b u i = y -A( f u i ) ĥu i .
Otherwise, go to Step 6.

• Step 6: Set j = j + 1. If j ≤ L then go to Step 4. Otherwise, go to Step 7. . Set Λ = f u * s and calculate the estimate signal ĥ = A † (Λ)y.

• Step 7: Set k = k + 1. If k ≤ |F i-1 |

If the arg max

||A H b k i-1 || 2 2 in the
Step 3 is calculated as in the OMP algorithm, the MMP algorithm is called Tree-based Orthogonal Matching Pursuit (TOMP) algorithm [START_REF] La | Signal reconstruction using sparse tree representations[END_REF].

Iterative Hard Thresholding (IHT)

The Iterative Hard Thresholding (IHT) algorithm [START_REF] Blumensath | Iterative Thresholding for Sparse Approximations[END_REF] is an iterative method that performs some thresholding function on each iteration. This algorithm can't be represented by Fig. 3

.3. Let ĥ0 = 0, i = 1, for each iteration: ĥi = H( ĥi-1 + A H (y -A ĥi-1 ); λ) (3.51)
where H(x; λ) is defined by:

H(x; λ) =    0, i f |x| λ x, i f |x| > λ (3.52)
The IHT algorithm can stop after a fixed number of iterations or it can terminate when the sparse vector does not change much between consecutive iterations, for example [START_REF]Iterative hard thresholding for compressed sensing[END_REF].

In addition to the algorithms presented in the previous paragraphs, several others can be found in the literature, among them, Back-tracking based Adaptive Orthogonal Matching Pursuit (BAOMP) [START_REF] Huang | Backtracking-based matching pursuit method for sparse signal reconstruction[END_REF], Chaining Pursuit (CP) [START_REF] Gilbert | Algorithmic linear dimension reduction in the 1 norm for sparse vectors[END_REF], Conjugate Gradient Iterative Hard Thresholding [START_REF] Blanchard | CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion[END_REF], Differential Orthogonal Matching Pursuit (D-OMP) [START_REF] Zhu | Tracking a dynamic sparse channel via differential orthogonal matching pursuit[END_REF], Denoising-based AMP (D-AMP) [START_REF] Metzler | From denoising to compressed sensing[END_REF], Fast Iterative Shrinkage Thresholding Algorithm (FISTA) [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm with application to wavelet-based image deblurring[END_REF], Forward-Backward Pursuit (FBP) [START_REF] Karahanoglu | Compressed sensing signal recovery via forward-backward pursuit[END_REF], Fourier sampling algorithm [START_REF] Gilbert | Improved time bounds for near-optimal sparse fourier representations[END_REF], Hard Thresholding Pursuit [START_REF] Foucart | Hard thresholding pursuit: An algorithm for compressive sensing[END_REF], Heavy Hitters on Steroids (HHS) [START_REF] Gilbert | One sketch for all: Fast algorithms for compressed sensing[END_REF], Iterative Half Thresholding Algorithm (IHTA) [START_REF] Xu | l 1/2 regularization: A thresholding representation theory and a fast solver[END_REF], Normalized Iterative Hard Thresholding [START_REF] Tanner | Normalized iterative hard thresholding for matrix completion[END_REF], l p -Regularized Least Squares Two Pass [START_REF] Pant | Two-pass l p -regularized least-squares algorithm for compressive sensing[END_REF], Orthogonal Approximate Message Passing (OAMP) [START_REF] Ma | Orthogonal AMP[END_REF], Sequential Least Squares Matching Pursuit (SLSMP) [START_REF] Li | Estimation and tracking of rapidly time-varying broadband acoustic communication channels[END_REF], Sparse Adaptive Orthogonal Matching Pursuit (SpAdOMP) [START_REF] Mileounis | An adaptive greedy algorithm with application to nonlinear communications[END_REF], Sparse Reconstruction by Separable Approximation (SpaRSA) [START_REF] Wright | Sparse reconstruction by separable approximation[END_REF], Stochastic Gradient Pursuit (SGP) [START_REF] Vlachos | Stochastic gradient pursuit for adaptive equalization of sparse multipath channels[END_REF],

Stochastic Search Algorithms [START_REF] Olshausen | Learning sparse codes with a mixture-of-gaussians prior[END_REF], Stein's Unbiased Risk Estimate Approximate Message Passing (SURE-AMP) [START_REF] Guo | Near optimal compressed sensing without priors: Parametric SURE approximate message passing[END_REF], Tree Search Matching Pursuit (TSMP) [START_REF] Lee | Sparse signal recovery via tree search matching pursuit[END_REF], Vector Approximate Message Passing (VAMP) [START_REF] Rangan | Vector approximate message passing[END_REF], Weighted Iterative Shrinkage Thresholding Algorithm (WISTA) [START_REF] Zhao | Deep neural network structured sparse coding for online processing[END_REF].

Many of these algorithms are derivations of those presented in the previous sections. Therefore, it was preferred in this thesis to give more details to the ones that were used as the basis for the techniques proposed in Chapter 5 and as well as the basis for other algorithms proposed in the literature.

Performance Discussion

In order to have a better understanding of the potential of each solution, some algorithms representative of each category were selected for further study. The performance comparison between these algorithms resulted in a published scientific paper [START_REF] Marques | A review of sparse recovery algorithms[END_REF].

From the Convex Relaxation category, the AMP and FISTA algorithms were implemented.

The BCS via RVM was implemented representing the Non-convex Optimization category. And finally, from the Greedy algorithms, the MP and OMP were implemented.

Let N s = 1000 be the number of realizations, the normalized mean squared error (NMSE)

described by (3.53) is used to evaluate the algorithms in terms of the size of the measured signal y (M) and the signal's sparsity.

NMSE = 1 N s ∑ h -ĥ 2 2 h 2 2 (3.53)
The system model is defined by (2.8), considering:

• N = 1024;
• SNR = 30 dB;

• A is i.i.d. Gaussian, with elements distributed N (0, M -1 );

• the sparse signal h to be estimated is Bernoulli-Gaussian, that is, its elements are i.i.d N (0, 1) with probability γ and the others are set to 0.

The results are compared to the theoretical performance bound Oracle Least Square (OLS), which has the previous knowledge of the non-zero tap positions. Let A s be the matrix generated by s columns of the matrix A related to the non-zero taps positions of the signal to be estimated, where s is the sparsity of h. The OLS calculates the non-zero coefficients of ĥ by applying the pseudo-inversion process in the matrix A s .

First, the algorithms performances are analyzed varying the size of M for γ = 0.05 as shown in Fig. 3.5 [START_REF] Marques | A review of sparse recovery algorithms[END_REF]. It can be seen that the performances of all the algorithms increase when the number of measurements M increases. However, it can be noticed that a low M value (M < N) allows the algorithms to recover the sparse signal resulting in low NMSE values. Among the algorithms analyzed, the BCS presents the best performance. Furthermore, its performance is close to the one achieved by the OLS. It confirms the good results achieved by the algorithms from the Bayesian theory [START_REF] Marques | A review of sparse recovery algorithms[END_REF].

The algorithms performances are also analyzed varying γ for M = 512 as shown in Fig. 3.6 [START_REF] Marques | A review of sparse recovery algorithms[END_REF].

According to Fig. 3.6, as the signal becomes less sparse (i.e. γ increases), the performances of all algorithms decrease, that is, the NMSE values increase. When γ is low, BCS is the algorithm that achieves the best performance (lower NMSE value), which is close to the one achieved by the OLS. However, when the signal to be estimated is less sparse (big γ values), FISTA shows a better performance in recovering the signal [START_REF] Marques | A review of sparse recovery algorithms[END_REF]. 3.2 shows the percentage of non-zero tap positions correctly found for the five algorithms analyzed [START_REF] Marques | A review of sparse recovery algorithms[END_REF]. The result of FISTA is not presented for M = 200 because in this scenario this algorithm did not converge. It can be observed that:

• when the M value increases, the percentage of non-zero tap positions correctly found increases.

• although AMP and FISTA algorithms present the highest percentage values for M = 400 and γ = 0.05, the algorithms BCS and OMP are the ones that achieve the best results in terms of NMSE (see Fig. 3.5). It means that even if BCS and OMP correctly find less non-zero tap positions than the algorithms AMP and FISTA, BCS and OMP are better able to estimate the non-zero coefficients resulting in lower NMSE values.

• when the γ value increases, that is, the signal become less sparse, the percentage of nonzero tap positions correctly found decreases. This occurs for all the algorithms analyzed and confirms what was suggested in Fig. 3.6.

Other performance comparisons between other algorithms can be found in the literature. Some of them are presented below.

A performance comparison of the SP, the OMP, the ROMP, the GOMP, and the GOAMP algorithms is made in [START_REF] Dhasmana | A survey of compressive sensing based greedy pursuit reconstruction algorithms[END_REF] for the reconstruction of an image. The recovery performance was analyzed in the form of Peak Signal to Noise Ratio (PSNR) value achieved and running time elapsed. From these simulations, the PSNR value is better when the GOAMP algorithm is used.

In [START_REF] Arjoune | Compressive sensing: Performance comparison of sparse recovery algorithms[END_REF], the authors compare the BCS, the BP, the GraDeS, the OMP, and the IHT algorithms to estimate a noisy sparse signal of length N = 1024. The metrics used were: phase transition diagram, recovery time, recovery error, and covariance. The results show that techniques of convex relaxation perform better in terms of recovery error, while greedy algorithms are faster, and Bayesian based techniques appear to have an advantageous balance of small recovery error and a short recovery time [START_REF] Arjoune | Compressive sensing: Performance comparison of sparse recovery algorithms[END_REF].

A comparison between the OMP and the modified LARS for solving LASSO algorithms is made in [START_REF] Hameed | Comparative analysis of orthogonal matching pursuit and least angle regression[END_REF] considering the solution accuracy and the convergence time. The results show that generally the OMP requires fewer iterations than the LARS to converge to the final solution, suggesting that the OMP is much faster than the LARS [START_REF] Hameed | Comparative analysis of orthogonal matching pursuit and least angle regression[END_REF]. However, for the cases where some columns of A are highly correlated, the OMP was considered less accurate than the LARS [START_REF] Hameed | Comparative analysis of orthogonal matching pursuit and least angle regression[END_REF].

In [START_REF] Wang | Generalized orthogonal matching pursuit[END_REF], the authors compare the GOMP, the OMP, the StOMP, the ROMP, and the CoSaMP algorithms for a measurement matrix A 128×256 generated by a Gaussian distribution N(0, 1/128).

The sparse signal varies from s = 1 to s = 70 and it is generated in two ways: Gaussian signals and pulse amplitude modulation (PAM) signals. The results show that the critical sparsity of the GOMP algorithm is larger than that of the OMP, the ROMP, the StOMP, and the CoSaMP algorithms [START_REF] Wang | Generalized orthogonal matching pursuit[END_REF].

Algorithms OMP, StOMP, CoSaMP, MMP, and BPDN are compared in [START_REF] Kwon | Multipath matching pursuit[END_REF] varying the SNR for two different sparsity values (s = 20 and s = 30). The 100 × 256 measurement matrix is generated by a Gaussian distribution. The results show that the MMP performs close to the OMP to s = 20, but for s = 30, the performance of the MMP is better [START_REF] Kwon | Multipath matching pursuit[END_REF]. Moreover, the running time of these algorithms is shown as a function of s. The MMP algorithm has the highest running time and the OMP and the StOMP algorithms have the lowest running time among algorithms under test [START_REF] Kwon | Multipath matching pursuit[END_REF].

In [START_REF] Chartrand | Iteratively reweighted algorithms for compressive sensing[END_REF], the authors compare the performance of the IRLS algorithm using the regularization.

The results show that for p = 1 the unregularized IRLS and regularized IRLS are almost identical but for p = 0 and p = 1/2, the regularized IRLS algorithm recovers the greatest range of signals.

The authors in [START_REF] La | Signal reconstruction using sparse tree representations[END_REF] compare the performance of the TOMP, the BP, and the OMP algorithms.

According to their results, TOMP needs less iteration than the OMP because the TOMP algorithm selects the whole tree at a time and not only one element. Moreover, the TOMP can achieve better results than the BP and the OMP in reconstruction quality [START_REF] La | Signal reconstruction using sparse tree representations[END_REF].

In [START_REF] Bai | High-speed compressed sensing reconstruction on FPGA using OMP and AMP[END_REF], the authors implement the algorithms OMP and AMP in FPGA. As the OMP processing time increases quadratically with the number of non-zero coefficients of the signal to be estimated, this algorithm is more suitable to recover very sparse signals. On the other hand, if the signal to be estimated has several non-zero components it is more efficient to use the AMP algorithm to recover the signal than the OMP.

The study of these sparse recovery algorithms led to the proposition of a greedy algorithm called Matching Pursuit based on Least Squares (MPLS) that is presented in Section 5.1. In addition, the good results of FISTA and the simplicity of ISTA stimulated the study of the neural network LISTA and others neural networks used to sparse signal recovery (see Chapter 4).

Basics on Deep Learning

A neural network (NN) is a connection of several neuron elements to a layered architecture (see Fig. 4.1). In each neuron element, several inputs are weighted summed with bias and it is fed into an activation function σ(.) [START_REF] Wang | Deep learning for wireless physical layer: Opportunities and challenges[END_REF]. Some activation functions are presented in Table 4.1 [START_REF] Wang | Deep learning for wireless physical layer: Opportunities and challenges[END_REF][START_REF] O'shea | An introduction to machine learning communications systems[END_REF]. The feed-forward neural network is illustrated in Fig. 4.2. Its output in the layer l is given by:

r l = σ(W l r l-1 + e l ) (4.1)
where

Θ l = [W l , e l ]
is the set of learnable parameters of the layer l. σ(.) introduces a non-linearity which is very important for the expressive power of the neural network [START_REF] O'shea | An introduction to machine learning communications systems[END_REF]. problems [START_REF] Borgerding | AMP-inspired deep networks for sparse linear inverse problems[END_REF]. Indeed, in [START_REF] Borgerding | AMP-inspired deep networks for sparse linear inverse problems[END_REF], the authors applied CNN to solve two 5G problems, but they did not obtain good results.

Once a neural network has been structured, it has to be trained. Given a set of training data, the NN is trained to minimize a loss function through an optimization algorithm, such as the Stochastic Gradient Descent (SGD) [START_REF] Robbins | A stochastic approximation method[END_REF] and Adam [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF]. There are two approaches to training: supervised and unsupervised.

Supervised training provides the network with the inputs and the corresponding outputs. In others words, the training data {(y d , h d )} D d=1 pairs based on signal statistics are used to train the parameters of the deep neural network (DNN) to accurately predict the unknown label ĥ associated with a newly observed feature y. The NN compares its resulting outputs with the desired outputs and then it adjusts its parameters to minimize the error. After training the neural network with a set of {(y d , h d )} D d=1 , the network can be used to predict the sparse signal h that corresponds to an input y. The learned network is implicitly dependent on the matrix A and the noise statistics [START_REF] Borgerding | AMP-inspired deep networks for sparse linear inverse problems[END_REF].

On the other hand, in an unsupervised training, the network has, in the training phase, the inputs without the corresponding outputs. For example Self-Organizing Maps which are also called Kohonen networks [START_REF] Kohonen | Self-organizing maps[END_REF][START_REF] Kohonen | The self-organizing map[END_REF]. Therefore, supervised learning requires prior training which makes difficult to implement the supervised NN in online processing and applications without training data. In contrast, unsupervised learning allows the use of NN for online processing when the learning procedure is fast enough.

The choice of the optimization algorithm, loss function, and activation function for a deep learning model influences on producing faster and accurate results. Moreover, the training data is very important to a good convergence of the NN.

Sparse recovery algorithms can be improved if they are combined with supervised deep learning. The literature reports different deep-learning approaches to solve sparse linear inverse problems [31-42, 185, 190, 191, 200-206]. For instance, it is possible to unroll/unfold a known iterative recovery algorithm into a neural network such as LISTA [START_REF] Gregor | Learning fast approximations of sparse coding[END_REF] (see Section 4.2.1) and LAMP [START_REF] Borgerding | Onsager-corrected deep learning for sparse linear inverse problems[END_REF] (see Section 4.2.2). These networks generally have numerical values as labels. Moreover, continuous and differentiable functions throughout the network structure allow the use of gradient-based learning methods to train network parameters [START_REF] Zhao | Deep neural network structured sparse coding for online processing[END_REF]. Deep unfolding can be summarized as "given a model-based approach that requires an iterative inference method, we unfold the iterations into a layer-wise structure analogous to a neural network" [START_REF] Hershey | Deep unfolding: Model-based inspiration of novel deep architectures[END_REF]. A number of trainable parameters are learned using techniques from deep learning.

One of the main advantages of using neural network in compressive sensing is the reduction of computational complexity in the recovery step (CS reconstruction). Compared to sparse recovery algorithms, it means fewer matrix multiplications and iterations required to estimate the signal [START_REF] Borgerding | Onsager-corrected deep learning for sparse linear inverse problems[END_REF]. Instead of solving an optimization problem at the receiver, the network is defined before and its parameters are optimized to minimize a loss function during the training phase. Even if the training phase can require a lot of computational resources to better fit the network, in a lot of cases the neural network is only fit once up front and this phase is not necessary to run during the reception, so it can be done offline [START_REF] Xin | Maximal sparsity with deep networks?[END_REF][START_REF] Molanes | Deep learning and reconfigurable platforms in the internet of things: Challenges and opportunities in algorithms and hardware[END_REF].

Neural Networks Presented in the Literature

This section addresses some neural networks reported in the literature applied to sparse signals estimation. Some of them are based on the idea of unfolding an iterative algorithm. Fig. 4.5 shows the neural networks that will be discussed in more details in this section. The sparse recovery algorithms that inspired them are also illustrated in this figure. After training the neural network with a set of {(y d , h d )} D d=1 , the network can be used to predict the h that corresponds to the input y.

To better understand the relation between ISTA and LISTA, we can rewrite (3.15) as (4.4): 2). In addition, the computational complexity of one layer of LISTA is essentially equal to one iteration of ISTA or AMP algorithms [START_REF] Borgerding | AMP-inspired deep networks for sparse linear inverse problems[END_REF]. Moreover, the estimates generated by the LISTA network need fewer matrix-vector multiplications than existing algorithms with optimally tuned regularization parameters (λ) [START_REF] Borgerding | AMP-inspired deep networks for sparse linear inverse problems[END_REF]. LISTA can reach the results achieved by ISTA with much fewer layers than the number of ISTA iterations. This can be seen in Section 5.5.2 and in the results presented in [START_REF] Borgerding | AMP-inspired deep networks for sparse linear inverse problems[END_REF],

ĥi = η st ĥi-1 + βA T b i-1 ; λ = η st ĥi-1 -βA T (A ĥi-1 -y); λ = η st ĥi-1 -βA T A ĥi-1 + βA T y; λ
where LISTA took only 16 layers to reach an NMSE of -35 dB, whereas AMP took 25 iterations and ISTA took 4402 iterations.

In [START_REF] Kamilov | Learning optimal nonlinearities for iterative thresholding algorithms[END_REF], the authors propose to use the cubic B-splines as shrinkage function in LISTA. Alternatively, the authors in [START_REF] Mahapatra | Deep sparse coding using optimized linear expansion of thresholds[END_REF] model the nonlinear activation function using a linear expansion of thresholds. In this thesis, other activation functions to be used in LISTA are analyzed in Section 5.5.

Learned Approximate Message Passing (LAMP)

The Learned Approximate Message Passing (LAMP) [START_REF] Borgerding | AMP-inspired deep networks for sparse linear inverse problems[END_REF][START_REF] Borgerding | Onsager-corrected deep learning for sparse linear inverse problems[END_REF] was inspired by AMP (see Section 3.1.6). Indeed, the neural network LAMP is constructed by unfolding the iterations of AMP.

Let

λ i = α i ||b i || 2 √
M , the output ĥi of the i-layer of LAMP is calculated by (4.7). It can be noticed that the parameter λ i varies with the b i , while in LISTA it does not. LAMP also differs from LISTA in the presence of the last term in (4.8) known as "Onsager correction". The function η depends on the problem setting as well as it occurs in AMP. ĥi = η( ĥi-1 In each layer two matrixvector multiplications are performed (with C i and A). Therefore, the computational and memory complexity of LAMP are ≈ 2N L MN and ≈ N L MN, respectively. In [START_REF] Borgerding | AMP-inspired deep networks for sparse linear inverse problems[END_REF], the authors also suggest one other version of LAMP where C is the same matrix in all layers resulting in a memory complexity ≈ MN. The function η H defined by (4.9) is also called in [START_REF] Wang | Learning deep l 0 encoders[END_REF] as Hard thrEsholding Linear Unit (HELU) function. It was chosen because it tends to produce highly sparse solutions and it does not penalize large values [START_REF] Wang | Learning deep l 0 encoders[END_REF]. However, during the training phase, η H is replaced by HELU σ (when σ → 0, HELU σ becomes η H ), that is, a continuous and piecewise linear function (see (4.10)). In [START_REF] Wang | Learning deep l 0 encoders[END_REF], the authors start with σ = 0.2 and after each epoch, σ is divided by 10.

+ C i-1 b i-1 ; λ i-1 ) (4.7) b i = y -A ĥi + || ĥi || 0 M b i-1 (4.8)
ĥi b i y + C i η α i b i 2 √ M . 0 M × A + + ĥi+1 b i+1 y λ i -
η H (x) =    0, i f |x| ≤ 1 x, i f |x| ≥ 1 (4.9) HELU σ (x) =                0, i f |x| ≤ 1 -σ (x-1+σ) σ , i f 1 -σ < x < 1 (x+1-σ) σ , i f -1 < x < σ -1 x, i f |x| ≥ 1 (4.10)
Dl 0 RE performs one matrix-vector multiplication with S in each layer. Its computational and memory complexity are ≈ N L N 2 and ≈ N 2 + MN, respectively. Comparing the IHT algorithm with Dl 0 RE, it can be seen some similarities. For instance, η H is the function (3.52) used in IHT with λ = 1. In addition, several similarities between LISTA (see Section 4.2.1) and the neural network illustrates in Fig. 4.9 can be noticed.

Learned Denoising-based Approximate Message Passing (LDAMP)

The Learned D-AMP (LDAMP) was proposed in [START_REF] Metzler | Learned D-AMP: Principled neural network based compressive image recovery[END_REF] inspired by the D-AMP algorithm [START_REF] Metzler | From denoising to compressed sensing[END_REF].

Let ĥi be the estimate of the signal h at iteration i and ĥ0 = 0, each iteration i of D-AMP calculates:

z i = y -A ĥi + z i-1 divD σi-1 ( ĥi-1 + A H z i-1 ) M (4.11) σi = ||z i || 2 √ M (4.12) ĥi+1 = D σi ( ĥi + A H z i ) (4.13)
where z i is an estimate of the residual, σi is an estimate of the standard deviation of that noise, D σi is the denoiser and divD σi-1 is the divergence of the denoiser [START_REF] Metzler | From denoising to compressed sensing[END_REF]. ReLU [START_REF] Metzler | Learned D-AMP: Principled neural network based compressive image recovery[END_REF]. Finally, the last layer uses c separate 3x3x64 filters to reconstruct the signal. Therefore, each layer i of LDAMP can be described by:

z i = y -A ĥi + z i-1 divD w i-1 ( σi-1 ) ( ĥi-1 + A H z i-1 ) M (4.14) σi = ||z i || 2 √ M (4.15) ĥi+1 = D w i ( σi ) ( ĥi + A H z i ) (4.16)
In LDAMP, only the denoiser weights w i are learned, differently from LISTA (see Section 4.2.1),

where the matrices S and B are learned during the training phase.

In [START_REF] He | Deep learning-based channel estimation for beamspace mmWave massive MIMO systems[END_REF], the authors consider the channel matrix as a 2D natural image and apply LDAMP which incorporates the denoising convolutional neural network (DnCNN) [START_REF] Zhang | Beyond a gaussian denoiser: Residual learning of deep CNN for image denoising[END_REF] for channel estimation in beamspace mmWave massive MIMO systems. The results indicate that the LDAMP network can achieve good performance for mmWave channel estimation.

Trainable ISTA (TISTA)

Trainable ISTA (TISTA) includes three parts: a linear estimator, a minimum mean squared error (MMSE) estimator-based shrinkage function, and a variance estimator [START_REF] Ito | Trainable ISTA for sparse signal recovery[END_REF][START_REF]Trainable ISTA for sparse signal recovery[END_REF]. Fig. 4.11 illustrates one layer of TISTA.

The recursive formula of TISTA can be described by [START_REF] Ito | Trainable ISTA for sparse signal recovery[END_REF]: ĥi+1 = η MMSE (r i ; τ 2 i ) (4.17)

ĥi y + A + η N M SE (r i ; τ 2 i ) τ 2 i γ i W ĥi+1 y - r i
r i = ĥi + γ i W(y -A ĥi ) (4.18) τ 2 i = v 2 i N (N + (γ 2 i -2γ i )M) + γ 2 i σ 2 N tr(WW T ) (4.19)
v 2 i = max ||y -A ĥi || 2 2 -Mσ 2 tr(A T A) , ε (4.20)
where ĥ0 = 0, σ 2 is the variance of the noise, W = A T (AA T ) -1 , γ i is a trainable parameter, and ε is a small value (e.g. ε = 10 -9 ). The MMSE shrinkage function η MMSE is chosen according to the prior distribution of the original signal h. The variables γ i control the variance of the MMSE shrinkage function.

The time complexity of TISTA per iteration is O(N 2 ), which is the same time complexity of ISTA and AMP [START_REF] Ito | Trainable ISTA for sparse signal recovery[END_REF]. TISTA performs two matrix-vector multiplications (with A and W) in each layer. Its computational and memory complexity are ≈ 2N L MN and ≈ 2MN, respectively.

Obtained results presented in [START_REF] Ito | Trainable ISTA for sparse signal recovery[END_REF] suggest that TISTA can be applied to different matrices A such as binary and Gaussian matrices. In addition, the resutls shows that TISTA converges faster than LISTA and AMP in several cases [START_REF] Ito | Trainable ISTA for sparse signal recovery[END_REF]. In [START_REF]Trainable ISTA for sparse signal recovery[END_REF], the authors propose two extensions of TISTA to deal with matrix A with nonzero-mean components or with a large condition number.

The condition number k of a matrix is defined as the ratio of the largest and smallest singular values, i.e., k = s 1 /s M [START_REF]Trainable ISTA for sparse signal recovery[END_REF]. In addition, an extension of TISTA to complex-field nonlinear inverse problems is proposed in [START_REF] Takabe | Complex field-trainable ISTA for linear and nonlinear inverse problems[END_REF].

Stein's Unbiased Risk Estimate based-Trainable Iterative Thresholding Algorithm (SURE-TISTA)

Let a divergence-free denoiser Î be constructed as (4.21) where C is a constant and I(.) is an arbitrary function [START_REF] Ma | Orthogonal AMP[END_REF].

Î(x t ) = C (I(x t ) -div{I(x t )x t }) (4.21)
Stein's unbiased risk estimate based-trainable iterative thresholding algorithm (SURE-TISTA)

was developed in [START_REF] Yao | SURE-TISTA: A signal recovery network for compressed sensing[END_REF] for sparse signal recovery problems. Fig. 4.12 illustrates a layer of SURE-TISTA. Each layer calculates:

ĥi = Î (r i-1 ; λ i ) (4.22) r i-1 = ĥi-1 + W(y -A ĥi-1 )
where ĥ0 = 0, W = N tr( ŴA) Ŵ, Ŵ = A T (AA T ) -1 , and λ i is a trainable parameter. C optimal is calculated based on SURE framework [START_REF] Yao | SURE-TISTA: A signal recovery network for compressed sensing[END_REF]. ĥi y

+ A + I(r i ; λ i ) Î(r i ; λ i ) C optimal W ĥi+1 y - r i Figure 4.
12 -One layer of the SURE-TISTA network.

As weel as TISTA, SURE-TISTA performs two matrix-vector multiplications (with A and W) in each layer. Its computational and memory complexity are ≈ 2N L MN and ≈ 2MN, respectively.

The results presented in [START_REF] Yao | SURE-TISTA: A signal recovery network for compressed sensing[END_REF] indicate that SURE-TISTA requires fewer learnable variables to achieve similar performance as LAMP. Moreover, SURE-TISTA outperforms TISTA and does not require error measure estimators nor prior information [START_REF] Yao | SURE-TISTA: A signal recovery network for compressed sensing[END_REF].

In addition to neural networks discussed in the previous paragraphs, many others have been reported in the literature in the recent years. The list below enumerates other neural networks that can be used to sparse signal estimation: DeepInverse [START_REF] Mousavi | Learning to invert: Signal recovery via deep convolutional networks[END_REF], Deep M-Sparse l 0 Encoder [START_REF] Wang | Learning deep l 0 encoders[END_REF], Deep

Neural Network-structured IHTA (DNN-IHTA) [START_REF] Zhao | Deep neural network structured sparse coding for online processing[END_REF], Deep Neural Network-structured WISTA (DNN-WISTA) [START_REF] Zhao | Deep neural network structured sparse coding for online processing[END_REF], DR2-Net [190], DeepNIS [START_REF] Li | DeepNIS: Deep neural network for nonlinear electromagnetic inverse scattering[END_REF], FompNet [START_REF] Bo | FompNet: Compressive sensing reconstruction with deep learning over wireless fading channels[END_REF], Learned Vector Approximate Message Passing (LVAMP) [START_REF] Borgerding | AMP-inspired deep networks for sparse linear inverse problems[END_REF], OAMP-Net [START_REF]A model-driven deep learning network for MIMO detection[END_REF], ReconNet [190], WDLReconNet [START_REF] Lu | WDLReconNet: Compressive sensing reconstruction with deep learning over wireless fading channels[END_REF].

These neural networks are not detailed here because some of them are more suitable for image estimation than for sparse channel estimation and others are variations from the NNs addressed in the sections above.

Discussion

This section presents a comparison between some NNs addressed in Section 4.2. Then an alternative solution to deal with complex numbers in NNs is exposed. Finally some challenges of the use of NN are discussed.

Comparison Between Some NNs

The choice of the NNs analyzed in this section was based on their representativeness or their use as a basis for other NNs. LISTA is one of the first neural network based on a sparse recovery algorithm presented in the literature. It inspired other authors to unfold known iterative recovery algorithms into neural network and apply it to sparse signal recovery.

These networks can outperform the results achieved by the original algorithm. For instance, one layer of LISTA, LAMP or TISTA has essentially the same computational complexity than one iteration of ISTA or AMP algorithms [START_REF] Borgerding | AMP-inspired deep networks for sparse linear inverse problems[END_REF][START_REF] Ito | Trainable ISTA for sparse signal recovery[END_REF]. However, sparse signal estimation using LISTA LAMP or TISTA can produce better estimates with fewer matrix-vector multiplications than using ISTA or AMP. Moreover, obtained results in [START_REF] Yao | SURE-TISTA: A signal recovery network for compressed sensing[END_REF] indicate that SURE-TISTA outperforms TISTA without require prior information nor error measure estimators.

Neural Network with Complex Number

In communication systems, normally the channel and the signals are complex. In generally, the deep networks are not adapted to deal with complex number. Let real(.) and imag(.) be the real and imaginary parts of a complex vector, respectively. In order to use neural network to estimate complex sparse signals, the modification presented in (4.23) can be applied.

y R =   real(y) imag(y)   , h R =   real(h) imag(h)   , n R =   real(n) imag(n)   , A R =   real(A) -imag(A) imag(A) real(A)   (4.23)
Therefore, (2.8) can be replaced by (4.24).

y R = A R h R + n R (4.24)

Challenges

Using neural network to sparse signal recovery takes advantage of potentially available training data. However, although the use of neural network appears to perform improvements for some applications, it presents some challenges. Maybe it can be necessary to train a specific network for each SNR value. Training at a low SNR does not allow to fit the best network in higher SNR scenarios [START_REF] O'shea | An introduction to machine learning communications systems[END_REF]. The design of the neural network architecture and the optimal choice of loss and activation functions are other difficulties related to neural networks. The quantity of the training data {(y d , h d )} D d=1 to be used is also important to better fit the network. Moreover, the majority of building blocks, techniques, and architectures for deep learning are based on real-valued operations and representations [START_REF] Trabelsi | Deep complex networks[END_REF]. However, in dealing with communication systems, complex numbers are used to represent the channel, noise, and received signal.

Therefore, the neural network has to be adapted to operate on complex numbers. One alternative is presented in Section 4.3.2.

The study of the LISTA led to the proposal of two improvements for this NN, both of which increase the performance of its estimation. The first one is to use the estimate of LISTA as a first result to estimate the non-zero tap positions of a sparse signal and then to calculate their values by pseudo-inversion process (see Section 5.3). The second one is to change the shrinkage function η st used in LISTA to other functions (see Section 5.5). In addition, the study of the neural networks addressed in this chapter motivated the proposition of a new neural network that is presented in Section 5.4. Before explaining the techniques developed in this work, some definitions will be rewritten here:

• As defined in Section 3.4, the Oracle Least Square (OLS) estimator is the LS with ideal knowledge of the sparse signal on both the number of non-zero elements and their positions.

Let A s be the matrix generated by s columns of the matrix A, where s is the sparsity of h.

The OLS calculates the non-zero coefficients of ĥ by applying the pseudo-inversion process in the matrix A s .

• The system model used in this chapter is defined by (2.8). Its parameter values are reported in each section of this chapter.

• The SNR is defined by (5.1)

SNR = E[||Ah|| 2 2 ] E[||n|| 2 2 ]
(5.1)

• In some sections below, the NMSE is used to evaluate the estimation performance. Equation (3.53) is rewritten here as (5.2) to defined NMSE.

NMSE = 1 N s ∑ h -ĥ 2 2 h 2 2 (5.2)
Moreover, in this thesis, "tap attribution" is defined as to give "1" to a tap which has a nonzero value and "0" to a tap that has a zero value. For example, let h be the sparse signal to be estimated, its "tap attribution" is given by h t . Let ĥ be the estimate and ĥt be its "tap attribution", the percentage of non-zero taps positions correctly found is P c = 4/5 = 80% ( number of blue "1" in ĥt / number of "1" in h t ) and the percentage of taps which had an improper attribution is P e = 3/20 = 15% ( number of red "0" and red "1" in ĥt / length of h t ). These definitions will be applied in Sections 5.3, 5.4 and 5.6. h = 0 0 0.87 0 1.4 0 0 0.2 1.2 0 0.9 0 0 0 0 0 0 0 0 0 (5.3) h t = 0 0 1 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 (5.4) ĥ = 0.3 0 1.2 0 0.9 0 0.8 0.3 0 0 0.8 0 0 0 0 0 0 0 0 0 (5.5) ĥt = 1 0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 (5.6)

Matching Pursuit based on Least Squares (MPLS)

The study of the algorithms presented in Chapter 3 led to the development of a new greedy algorithm, called Matching Pursuit based on Least Squares (MPLS) [START_REF] De Paiva | Sparsity analysis using a mixed approach with greedy and LS algorithms on channel estimation[END_REF]. The MPLS algorithm builds upon the MP algorithm to find the positions of the non-zero signal taps. Similarly to the MP algorithm, each iteration of the MPLS algorithm consists in finding the column a k i ∈ A which is best aligned with the residual vector b i-1 ( b 0 = y) and the selection is performed according to:

k i = arg max l |a l H b i-1 |, l = 1, 2, ...., N (5.7)
The difference between the MP and the MPLS algorithms lies in how the values assigned to the non-zero signal taps are calculated. The MP algorithm estimates the signal as the projection values, while the MPLS algorithm does this estimation through the LS algorithm in the end of the algorithm.

Consider Λ i the index set of the best aligned columns of A until the iteration i, Λ i is updated by:

• If k i / ∈ Λ i-1 , the index set is updated as Λ i = Λ i-1 ∪ k i . • Otherwise, Λ i = Λ i-1 .
Then, the residual vector's projection along this direction is removed and a new residual vector is computed as (5.8).

b i = b i-1 -P a k i b i-1 = b i-1 - (a k i H b i-1 )a k i ||a k i || 2 2 (5.8)
After reaching the stop criterion, the signal is estimated by (5.9), where T is the number of iterations and A(Λ T ) is a submatrix of A consisting of the a i columns with i ∈ Λ T . ĥ = A † (Λ T )y (5.9)

Application Case

The performance of MP, MPLS and OMP algorithms for sparse channel estimation were evaluated and compared to the theoretical performance bound OLS.

The Mean-Square Deviation (MSD) described by (5.10) is used to evaluate the algorithms in terms of Sparsity (S) variation, where N s is the number of channel simulations.

MSD = 1 N s ∑ ||h -ĥ|| 2 2
(5.10)

The system model is defined by (2.8), considering:

• N = 120.

• SNR = 10 dB.

• A stands for the M × N measurement matrix. The ith column of A is denoted a i . A is a Toeplitz matrix determined by the training sequence c = [c 1 , c 2 , ..., c M ] T where c i is a QPSK value.

• Each element of the sparse signal h to be estimated is characterized by h i = s i d i . The complex-valued vector d = [d 1 , d 2 , ..., d N ] T characterizes the path gains as a complex gaussian distribution, while the binary vector s = [s 1 , s 2 , ..., s N ] T describes the channel paths.

Each s i ∈ {0, 1} denotes whether there is a non-zero channel tap at index i. The elements of the vector s correspond to the combination of the possible positions of the non-zero elements in the vector h, chosen randomly and with a number of elements defined by the sparsity of the channel.

• n is the Additive White Gaussian Noise (AWGN).

Estimation Performance

Comparisons of sparse channel estimation algorithms reported in the literature take into account only one channel with its fixed position of non-zero channel taps [START_REF] Carbonelli | Sparse channel estimation with zero tap detection[END_REF][START_REF] Cotter | Sparse channel estimation via matching pursuit with application to equalization[END_REF][START_REF] Huang | An improved compressed sensing reconstruction algorithm used in sparse channel estimation[END_REF]. More generally, performance analyses reflect only a fixed scenario. To obtain better precision, N s = 5000 sparse channels with length N = 120 were simulated for each point. Furthermore, performance analysis of the proposed algorithm are performed under a variety of scenarios by varying the sparsity of the channel, the length of the training sequence and the stopping criterion. When N it = 2S, the MPLS and the OMP algorithms have similar results in terms of MSD until 16 non-zero channel taps, but it should be noted that the MPLS algorithm achieves these results with lower complexity than the OMP algorithm. For S < 10, MP, OMP, and MPLS algorithms lead to similar results. Therefore, for this range of S values, MP algorithm is preferable due to its lower complexity.

Notice that, for small values of S and N it = S, the MSD of the OMP and MPLS algorithms are close to the one achieved by OLS. This means that both algorithms find almost all correct positions of the non-zero channel taps. Moreover, comparing the results for N it = 2S and N it = S, it can be seen that when the stop criterion is exactly the number of non-zero channel taps (N it = S), the MSD of both OMP and MPLS algorithms decrease unlike what happens with the MP algorithm.

Given that the MP and the MPLS algorithms choose the non-zero taps positions in the same way, different MSD values obtained are likely due to the value assigned to the non-zero channel taps. On the other hand, assigning the projection value to the channel estimation value (which is done by the MP algorithm) has a very damaging effect on channel estimation. This does not occur with MPLS algorithm, since it finds the correct positions of the non-zero channel taps and estimates their values using the LS algorithm, thus approaching to the results of the OLS estimation. Table 5.1 shows the amount of channels for which the algorithms found the correct positions of non-zero channel taps considering stopping criteria SC, N s = 5000, S = 6, and SNR = 10 dB. This table reinforces the conclusions from Fig. 5.1. Indeed, even if the MP algorithm finds the non-zero channel taps properly, it leads to higher MSD value compared to those from the MPLS and the OMP. It is worth mentioning that for small values S, a smaller M value can be used with the OMP and the MPLS algorithms without greatly increasing the MSD value.

These results points out an advantage of using algorithms that take into account the sparsity of the channel. It is noted that the OMP and the MPLS algorithms have similar results in terms of MSD, with the advantage that the MPLS algorithm is less computationally demanding.

Application of the CS on Wideband HF Channel Estimation

This section analyses the Wideband HF Channel Estimation using the algorithms MPLS, MP and OMP.

The High Frequency (HF) band ranges from 3 to 30 MHz and provides Beyond Line Of Sight and long-distance (often intercontinental) communications without the use of satellites or radiorelay, with low operational costs in comparison to fixed or satellite communication systems. HF radio communications are widely used for civilian and military applications on long-distance communications, mainly in remote regions and in emergency scenarios such as natural disasters [START_REF] Heidarpour | Multicarrier HF communications with amplify-andforward relaying[END_REF].

HF channel models are characterized by several parameters related to the behavior of the ionosphere. In general, a stochastic behavior that represents the different possible ways for the transmission to reach the receiver is modeled. Given the HF transmission characteristics, sometimes it is possible to establish transmissions from some tens of kilometers near vertical incidence skywave (NVIS) until distances far over-the-horizon (OTH) of the order of tens of thousands of kilometers [START_REF] Hervás | Channel sounding and polarization diversity for the NVIS channel[END_REF]. This large variety of scenarios brings great differences, for example, in delay scattering of the received signal, which could be of an order of 10 ms [START_REF] Mitola | Cognitive Radio Architecture: The Engineering Foundations of Radio XML[END_REF].

Several standards have been developed to standardize HF communications [216,217]. In traditional systems, the bandwidth of HF communications is very narrow (3 kHz) and the transmission rate is very low, about 600 bps or 2400 bps [217]. However, with the increasing amount of data transmission, it is necessary to increase the transmission rates, which requires a bigger bandwidth of HF communications. For example, the MIL-STD-188-110C in its Appendix D establishes the characteristics of the waveforms for transmission in wideband HF channels with bandwidth up to 24 kHz and data rates ranging from 75 bps for the lowest 3 kHz rate to 120 kbps for the highest 24 kHz rate [217]. The wideband HF channel is also used in spread spectrum communication, that is, in situations where stealthy and robust communications are required [START_REF] Laraway | HF band filter bank multi-carrier spread spectrum[END_REF].

The HF channel is a time-varying fading channel, involving time delay, Doppler frequency shift, interference, and noise. In a HF channel, the transmitted signal travels over several paths with different delays to the receiver via single or multipath reflects from the ionosphere (see Fig. 5.

3).

This channel is characterized by multipath propagation and fading as in (5.11) where h l (t, τ) is the impulse response for one of different ionospheric propagation paths (or reflecting ionospheric layers); l, t, and τ are independent variables for time and delay [START_REF] Mastrangelo | A new wideband high frequency channel simulation system[END_REF].

Ionosphere Sky Wave

Direct Wave Ground Wave Figure 5.3 -Types of radio propagation: sky wave (HF), direct wave and ground wave.

h(t, τ) = L-1 ∑ l=0 h l (t)δ(τ -τ l ) = L-1 ∑ l=0 h l (t, τ) (5.11)
The basic concepts of wideband HF channels are investigated in [START_REF] Belknap | Adaptive signal processing for ionospheric distortion correction[END_REF]. Some laboratories have conducted several wideband HF propagation measurement experiments useful in the channel model development process [START_REF] Basler | HF channel probe[END_REF][START_REF] Furman | Wideband HF channel availability -measurement techniques and results[END_REF]. A wideband HF simulation system is described in [START_REF] Mastrangelo | A new wideband high frequency channel simulation system[END_REF],

the wideband HF channel model proposed is more appropriate than the Watterson channel model for representing wideband HF channels.

The Watterson channel model [START_REF] Watterson | Experimental confirmation of an HF channel model[END_REF] neglects the time delay spread and the time delay of each path has a single value. Hence, it can not be used as a wideband HF channel model, because the effects of delay time spread, Doppler frequency shift, Doppler spread and variation of Doppler shift with delay must be described in the wideband HF channel model. To address these characteristics, for each propagation path, the model of the impulse response is given by [START_REF] Mastrangelo | A new wideband high frequency channel simulation system[END_REF]:

h l (t, τ) = P l (τ)D l (t, τ)Ψ l (t, τ) (5.12)
where P l (τ) is the delay power profile (DPP) that determines how the impulse response behaves, its square root P l (τ) describes the shape in delay dimension, D l (t, τ) is the deterministic phase function describing the Doppler shift of each path, and Ψ l (t, τ) is the stochastic modulation function [START_REF] Mastrangelo | A new wideband high frequency channel simulation system[END_REF].

τ c τ L τ U A A f σ c σ τ
Delay Time (µs) Amplitude controls the symmetry of the profile, and Γ(.) is the Gamma function, P l (τ) is defined by [START_REF] Mastrangelo | A new wideband high frequency channel simulation system[END_REF]:

P l (τ) = A α α+1 ∆Γ(α + 1)
z α e -αz (5.13)

z = τ -τ c ∆ + 1 > 0 (5.14)
Let f S be the Doppler shift at τ c and b be the rate of change of the Doppler shift between τ L and τ c , the deterministic phase function D l (t, τ) can be given by [START_REF] Mastrangelo | A new wideband high frequency channel simulation system[END_REF]:

D l (t, τ) = e i2π[ f S +b(τ-τ c )]t (5.15)
The stochastic modulation function Ψ l (t, τ) describes the fading of the impulse response.

Ψ l (t, τ) is independent in delay τ, correlated in time t. It is defined in terms of its resultant Doppler spread width and spectral shape [START_REF] Mastrangelo | A new wideband high frequency channel simulation system[END_REF]:

Ψ t = x t + iy t (t = 0, 1, 2, ...) (5.16)
where x t and y t are the independent random variables generated by independent random variables ρ t and ρ t [START_REF] Yan | Prediction of the HF ionospheric channel stability based on the modified ITS model[END_REF]:

x t = ρ t + (x t-1 -ρ t )λ
(5.17)

y t = ρ t + (y t-1 -ρ t )λ (5.18)
x 0 = (1λ)ρ 0 (5.19)

y 0 = (1 -λ)ρ 0 (5.20) λ = exp[-(∆t)σ f ] (5.21)
Ψ l (t, τ) can be generated as random variables having an autocorrelation function with Gaussian shape or Lorentzian shape [START_REF] Mastrangelo | A new wideband high frequency channel simulation system[END_REF][START_REF] Yan | Prediction of the HF ionospheric channel stability based on the modified ITS model[END_REF]. Since the HF transmissions have a small number of arriving rays, the HF channel can be seen as a tapped delay line in the delay spread domain. This section investigates the wideband HF channel estimation using sparse recovery algorithms.

In order to do this, the system model is defined by (2.8), where y = [y 1 , y 2 , ..., y M ] T is the

received signal, h = [h 1 , h 2 , ..., h N ] T

Wideband HF Channel A

The wideband HF Channel A is a case of near vertical incidence skywave (NVIS). It is a radio propagation mode which involves the use of antennas with a very high radiation angle. Channel A has 2 propagation paths with delay spread of 10 µs and 200 µs separated by 0.8 ms. These channel model parameters adjust the scattering function of the simulated channel to the scattering function of the reported measured channel presented in [START_REF] Wagner | Channel spread parameters for the highlatitude, near-verticalincidence-skywave HF channel: Correlation with geomagnetic activity[END_REF].

The comparison of the LS, the MP, the OMP, and the MPLS algorithms in terms of MSD performance versus the number of iterations (N it ) is shown in Fig. 5.6. The quantity of the acquired measurement is M = 40.

It can be noticed that after some iterations, the MSD value of the MP, the MPLS, and the OMP algorithms have increased with each new iteration. It occurs because these algorithms do not know the exact channel's sparsity (S) neither the exactly S non-zero tap positions. In fact, the wideband HF Channel A has few non-zero taps, so when these algorithms choose more non-zero taps, they are choosing tap positions with almost only the noise influence or re-selecting (it can occur with the MP and the MPLS algorithms) a tap and increasing the noise influence in this tap.

The LS algorithm gives the worst channel estimate because it does not consider the channel sparsity in its estimations. Then, the bad estimation influence is given in almost all taps for the channel estimate. Therefore, it is possible to see that if the MP algorithm is used, the MSD is lower. This occurs because this algorithm uses the sparsity characteristic of the channel to better estimate it. Moreover, if MP selects more non-zero tap positions than the sparsity S of the signal to be estimated, MP attributes a small value to these positions. It differs from the MPLS that uses the pseudo-inversion process to calculate its values and the OMP that in each new iteration chooses a new non-zero position, so when N it > S, the OMP is necessarily increasing the MSD value.

Wideband HF Channel B

The wideband HF Channel B has 4 propagation paths and each path has a delay spread of 100 µs.

One example is showed in Fig. 5.5. To obtain better precision, simulations in this work consider 5000 wideband HF channels where the delay position of each path was chosen randomly in each simulation.

The comparison of the LS, the MP, the OMP, and the MPLS algorithms in terms of MSD performance versus the number of iterations (N it ) is shown in Fig. 5.7. The quantity of the acquired measurement is M = 40.

It can be seen that for S < 6, the MP, the MPLS, and the OMP algorithms have similar results in terms of MSD, but for S > 6, the MP algorithm achieves a lower MSD value than the MPLS and the OMP algorithms. It can be explained due to the bad estimation influence in the taps which would be zero or almost zero. Besides this, the MPLS and the OMP algorithms use the LS solution to estimate the tap values. Then, the bad estimation influence goes to almost all taps. Otherwise, the MP algorithm gives the bad estimation influence from a bad tap selected only in this tap value estimate. The results suggest that wideband HF channels could be considered sparse in the delay spread domain. Simulations have shown that the use of a sparse recovery algorithm that considers the channel's sparsity achieves a better estimation performance than others that do not take into account the channel's sparsity.

Proposition to Improve the LISTA Performance

This section discusses a solution to improve the LISTA estimation performance. Fig. 5.9 shows an example of a sparse signal h and its estimate ĥ given by N L = 20 layers of LISTA [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF]. As can be seen, LISTA can estimate almost all the non-zero tap positions relatively well. However, LISTA improperly attributes non-zero values to several zero-value taps, so negatively impacting the estimation accuracy. From Fig. 5.9, it can be noticed that using an appropriate threshold µ allows to avoid undue non-zero values. With this in mind, Fig. 5.10 shows the general schema of the proposed sparse recovery approach which is called in this thesis as "Tech. 1" [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF]. The first step consists of LISTA implementation, which produces the estimate ĥ. The second step ("Selection") takes into account α and ĥ to produce the vector v . This step aims to use a threshold µ as presented in Fig. 5.9. Let g be the number of non-zero taps of ĥ, E be the biggest absolute tap value of ĥ and α be a positive value, the elements of the vector v are calculated by:

LISTA Selection l2 Optimization {(y d , h d )} D d=1 ĥ α v v
v (i) = 1, i f ĥ(i) > µ v (i) = 0, i f ĥ(i) ≤ µ (5.22)
where µ = αE.

That is, this step generates a signal v with j elements 1 where j ≤ g ≤ N. The positions of these j non-zero elements will be the same positions of the non-zero elements of v.

Let G(x) be the matrix M × K composed by only K columns of the matrix A correlated to the positions of the non-zero elements of x. The function U(x) is defined by:

U(x) = G † (x)y = G T (x)(G(x)G T (x)) -1 y (5.23)
Finally, step "l 2 Optimization" calculates the non-zero elements of v by U(v ). Then, the estimate v of the sparse signal h is calculated by attributing the values of the vector generated by U(v ) into the positions i where v (i) = 1.

Application Case

The normalized mean squared error (NMSE) described by (5.2) is used to evaluate the proposition of improvement of LISTA performance ("Tech. 1"). N s is the number of realizations, which corresponds to the number of different h to be estimated. In this work, N s = 10000.

The proposed sparse recovery approach considers the system model defined in (2.8), where:

• N = 120.

• M = 60.

• A is i.i.d. Gaussian, with N (0, M -1 ).

• h is Bernoulli-Gaussian. Its elements are i.i.d N (0, 1) with probability γ = 0.1 and the others are set to 0.

• SNR = 30 dB. 3) using the Adam optimizer [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF].

Estimation Performance

Fig. 5.11 presents the obtained NMSE as a function of the LISTA's number of layers N L . The curve LISTA std (in blue) represents the NMSE values considering ĥ as the estimate of the sparse signal h, that is, the output of the first step in Fig. 5.10 [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF]. The curve in which α = 0.0 considers the positions of the non-zero taps of ĥ as being those of non-zero taps of the v (g = j). However, the non-zero coefficients v differ from those of ĥ, they are calculated by (5.23). The other curves stand for NMSE values considering different values of α used in the step "Selection". Fig. 5.11 also presents the theoretical performance bound Oracle Least Square (OLS). As expected, increasing the number of layers makes the NMSE values decrease. Furthermore, from Fig. 5.11, it can be seen that using the steps proposed in Fig. 5.10 the estimation performance can be improved (NMSE values decrease) [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF].

As it is showed in Fig. 5.11, with α = 0.02, the NMSE value can decrease up to 5.9 dB compared to LISTA std . This occurs because, even if LISTA chooses good parameters Θ, the estimate ĥ given by LISTA has more non-zero taps than h, leading to worse NMSE values. Therefore, after the step "Selection", the number of the non-zero tap positions decreases and the step "l 2 Optmization" calculates their values using LS algorithm resulting in lower NMSE values. This conclusion is reinforced by Fig. 5.12 [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF]. Fig. 5.12 presents the percentage of taps which had an improper tap attribution, that is, the algorithm attributes a non-zero value to a tap that should have a zero value or the algorithm attributes a zero value to a tap which should have a non-zero value. It can be observed that only Furthermore, it can be noticed that to achieve NMSE = -20 dB only 4 layers are required in Case 3. Nevertheless, 8 layers are required if the steps proposed in Fig. 5.10 aren't applied (Case 1), so increasing the training phase time and also increasing the number of matrix-vector multiplications required in the evaluation phase.

These results show that applying the two steps proposed after the LISTA output may lead to better estimations (lower NMSE values) and fewer layers of the neural network than directly consider the output given by LISTA as the estimate of the signal of interest. However, even if these steps better estimate the sparse signal, the threshold used can set a zero value to a tap that should have a non-zero value. With this in mind, a new neural network is proposed and described in Section 5.4 to improve the sparse signal estimation focuses on finding the non-zero tap positions.

The steps proposed in Fig. 5.10 can be applied in other neural networks. For instance, it is possible to change the first step "LISTA" for another neural network for example LAMP and to use the estimate given by LAMP as ĥ in Fig. 5.10.

Proposed Neural Network

This section describes the proposed neural network to sparse signal estimation. Fig. 5.13 illustrates the proposed neural network with N L layers. In this thesis, this network is also called "Tech. 2" [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF]. The aim of this network is to estimate the non-zero tap positions of the sparse signal instead of directly estimate its elements. Once the non-zero tap positions is estimated by the proposed network, their element values are computed solving the least square problem. The output pi of the i-layer of the proposed network is given by: pi = η r (S pi-1 + Cy; λ i ) (5.24) In this thesis, two different η r functions are used: η st and η pwl . The first one, η r = η st , is the same function used in LISTA and defined by (3.16). On the other hand, η r = η pwl is defined by (5.26), where θ = {θ 1 , θ 2 , θ 3 , θ 4 , θ 5 } [START_REF] Guo | Near optimal compressed sensing without priors: Parametric sure approximate message passing[END_REF].

η r C y S p1 + η r S p2 + η r . . . S p3 pNL-1 + η r . . . f pNL Q p p
η pwl (x; θ) =          θ 3 x, i f |x| ≤ θ 1 sgn(x)[θ 4 (|x| -θ 1 ) + θ 3 θ 1 ], i f θ 1 < |x| ≤ θ 2 sgn(x)[θ 5 (|x| -θ 2 ) + θ 4 (θ 2 -θ 1 ) + θ 3 θ 1 ], i f θ 2 < |x| (5.26)
After the last layer of the proposed neural network, two more steps are performed (see Fig. 5.13):

• f : it is the bounded function defined by (5.27) and illustrated in Fig. 5.14. This function was chosen because it is a symmetric function and it generates only values

∈ [0, 1] resulting in p (i) ∈ [0, 1]. f (x) = |tanh(x)| = | e x -e -x e x + e -x | (5.27) -2 -1 1 2 1 x f (x) Figure 5.14 -f (x) = |tanh(x)|.
• Q: the vector p is transformed into the vector p composed by only elements 0 and 1. Let τ ∈ [0, 1], so:

p(i) = 1, i f p (i) ≥ τ p(i) = 0, i f p (i) < τ (5.28)
After the proposed neural network, p is the estimate of the non-zero tap positions of ĥ. In other words, p(i) = 0 corresponds to the taps of ĥ which have a 0 value and p(i) = 1 represents the taps of ĥ which have a non-zero value.

The non-zero elements of ĥ are calculated through the least square solution. In other words, the non-zero elements of the estimate ĥ of the sparse signal h are calculated by U(p) (see (5.23))

and compose the vector u. Then, the estimate ĥ is calculated by attributing the values of the vector u into the tap positions of the non-zero elements of p.

The major differences between LISTA and the proposed neural network are [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF]:

• While LISTA directly estimates ĥ, the proposed neural network estimates the tap positions of the non-zero elements of ĥ.

• In order to estimate the non-zero tap positions, two other "steps" are introduced after the last layer of the network (see Fig. 5.13).

• The element values of ĥ aren't directly calculated by the proposed neural network. They are calculated through the least square solution based on the proposed neural network output.

• The training data is different. In LISTA it is composed by sparse signals h d with different element values, while in the proposed neural network it is composed by the non-zero position vector t d , that is, t d has only 0 or 1 as element values.

Concerning the training phase, the parameters are learned in two steps. Firstly, only the parameter λ i of layer i is learned. Then a global learning is performed, that is, all the parameters (C, S, λ 1 , λ 2 , . . ., λ i ) are re-learned.

Application Case

This section presents an application case of the proposed neural network. The NMSE described by (5.2) is used to evaluate the proposed neural network performance in terms of the number of layers (N L ). Moreover, the percentage of improper "tap attribution" is also analyzed (see definition in Section 5.3.2).

The system model parameters are the same described in Section 5.3.1 and τ = 0.2. Training data sets {(y d , t d )} D d=1 with D = 10000 were used. An independent test set with a size of 10000 from the same distribution are also used. Finally, the parameters of the network were calculated minimizing the loss function described by (5.25) using the Adam optimizer.

Estimation Performance

The curves Tech. 1 and LISTA std showed in Fig. 5.15 and Fig. 5.16 are the same as those presented in Fig. 5.12 and Fig. 5.11, respectively [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF]. They were reproduced here to better compare the results achieved by the proposed neural network. Fig. 5.15 presents the percentage of taps which had an improper attribution [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF]. It can be noticed that the proposed neural network (curves Tech. 2 η st and Tech. 2 η pwl ) better estimates the non-zero tap positions. This occurs because it was trained focused on finding the non-zero tap positions instead of estimate the tap values (which is the case of LISTA). Fig. 5.16 presents the obtained NMSE as a function of the number of layers N L [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF]. The performance obtained with the proposed neural network is also compared to LISTA, OLS and the results achieved in Section 5.3.2 with α = 0.02 (curve Tech. 1).

From Fig. 5.16, it can be seen that the proposed neural network (curves Tech. 2 η st and Tech. 2 η pwl ) improves NMSE values compared to LISTA (curve LISTA std ). Indeed, using η r = η pwl (curve Tech. 2 η pwl ) the NMSE value can decrease up to 10.8 dB compared to LISTA std and the results achieved are close to OLS. On the other hand, when η r = η st , Tech. 2 achieves similar results in terms of NMSE when compared to the one achieved in Section 5.3.2 (curve Tech. 1).

When η r = η pwl , more parameters have to be calculated in the training phase compared to η r = η st . However η r = η pwl enables the proposed neural network be better adjusted to sparse estimation requiring few layers. In the simulations above, the channels in the sparse signal used in the training phase and the evaluation phase are generated with the same statistics. However, in real-world applications, mismatches may occur between the two phases. Therefore, it is essential for the trained models to be relatively robust to these mismatches.

In the next simulations, the impact of variation in statistics of the sparse signal used during training phase and evaluation phase is analyzed. Fig. 5.17 shows the obtained NMSE when the signal to be estimated and the signals used during the training phase have different γ values [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF]. N L = 9 and the training data has γ = 0.1. As expected, when the signal to be estimated is less sparse (γ > 0.1) than the signals used in the training data (γ = 0.1), the NMSE values achieved by "Tech. 1" and "Tech. 2" dissociate themselves from the NMSE of the OLS. However, it should be highlighted that "Tech. 2 η pwl " leads to better NMSE values suggesting that it has some degree of robustness when sparsity mismatch occurs.

Shrinkage Functions in LISTA

This section explores alternative shrinkage functions to be used in LISTA. The objective is to analyze their impact in terms of estimation quality.

The traditional shrinkage function η st used in LISTA is defined by (3.16) and it is shown in ity [START_REF] Kamilov | Learning optimal nonlinearities for iterative thresholding algorithms[END_REF]. As an alternative to these solutions, three shrinkage functions controlled by a small number of learnable parameters that can vary across the layers of the LISTA network are considered here:

Exponential (η exp ): Let θ = {θ 1 , θ 2 , θ 3
}, the exponential shrinkage function is defined by [START_REF] Guo | Near optimal compressed sensing without priors: Parametric sure approximate message passing[END_REF]:

η exp (x; θ) = θ 2 x + θ 3 xexp - x 2 2θ 2 1 (5.29)
Piecewise Linear (η pwl ): Let θ = {θ 1 , θ 2 , θ 3 , θ 4 , θ 5 }, this function has five segments [START_REF] Guo | Near optimal compressed sensing without priors: Parametric sure approximate message passing[END_REF]:

η pwl (x; θ) =          θ 3 x, i f |x| ≤ θ 1 sgn(x)[θ 4 (|x| -θ 1 ) + θ 3 θ 1 ], i f θ 1 < |x| ≤ θ 2 sgn(x)[θ 5 (|x| -θ 2 ) + θ 4 (θ 2 -θ 1 ) + θ 3 θ 1 ], i f θ 2 < |x| (5.30)
Spline (η spl ): The spline shrinkage function is defined by:

η spl (x; θ) = θ 2 x + θ 3 xβ x θ 1 (5.31)
where θ = {θ 1 , θ 2 , θ 3 } and β is the cubic B-spline [START_REF] Unser | Splines: a perfect fit for signal and image processing[END_REF]:

β(z) =          2 3 -|z| 2 + |z| 3 2 , i f 0 ≤ |z| ≤ 1 1 6 (2 -|z|) 3 , i f 1 ≤ |z| ≤ 2 0, i f 2 ≤ |z| (5.32)
In Fig. 5.18, each color represents a different set of parameters used in each shrinkage function.

Application Case

The normalized mean squared error (NMSE) described by (5.2) is used to evaluate ISTA and LISTA estimation performance in terms of the number of iterations (N it ) and number of layers (N l ), respectively. N s is the number of realizations. In this work, N s = 10000.

The system model is defined by (2.8), considering:

• N = 120.

• M = 60.

• A is i.i.d. Gaussian, with elements distributed N (0, M -1 ).

• h is Bernoulli-Gaussian, that is, its elements are i.i.d N (0, 1) with probability γ = 0.1 and the others are set to 0.

• SNR = 30 dB.

First, the parameters dependence in ISTA performance is verified. Next, the LISTA performance is analyzed for the shrinkage functions presented in Section 5.5. The results are compared to the theoretical performance bound OLS. This figure leads to the following observations [START_REF] Marques | Nonlinear functions in learned iterative shrinkage-thresholding algorithm for sparse signal recovery[END_REF]:

• Many iterations are required for ISTA convergence.

• In all considered cases, ISTA does not converge to a NMSE value close to the one achieved by OLS.

• ISTA converges to different NMSE values at different number of iterations depending on the β and λ values.

These results highlight the importance of the parameters choice as they highly influence the ISTA performance in sparse signal estimation. Moreover, they point out that even with a lot of iterations, ISTA does not give an estimation result close to the one achieved by the theoretical performance bound OLS.

LISTA Performance

In order to analyze the LISTA estimation performance, training data set {(y d , h d )} D d=1 with D = 10000 was used. For the testing phase, another set with a size of 10000 was used. In both phases, sets were generated independently with the same distribution parameters.

During the training phase of LISTA, the network adapts the parameters minimizing the loss function (4.3) through the Adam optimizer. Therefore, it is not necessary to choose the ISTA parameters β and λ, LISTA learns its parameters during the training phase. From this figure, it can be seen that [START_REF] Marques | Nonlinear functions in learned iterative shrinkage-thresholding algorithm for sparse signal recovery[END_REF]:

• The NMSE values achieved by LISTA with the piecewise linear, exponential, and spline shrinkage functions are better than those achieved by LISTA with the traditional shrinkage function η st .

• The use of piecewise linear, exponential, and spline shrinkage functions leads to NMSE value decrease up to 9 dB compared to the traditional shrinkage function.

• The use of one of the shrinkage functions presented in Section 5.5 allows LISTA to achieve performance close to OLS in a reasonable number of layers.

• While the traditional shrinkage function (3.16) has only one parameter that is adjusted for each layer, the functions of Section 5.5 have three or five parameters. The results suggest that increasing the degree of freedom of the shrinkage function, better results in terms of NMSE can be achieved.

The computational complexity of one layer of LISTA and one iteration of ISTA are essentially the same [START_REF] Borgerding | AMP-inspired deep networks for sparse linear inverse problems[END_REF]. Comparing ISTA and LISTA estimation performances by the results presented in Figs. 5.19 and 5.20, respectively, it can be noticed that [START_REF] Marques | Nonlinear functions in learned iterative shrinkage-thresholding algorithm for sparse signal recovery[END_REF]:

• Applying LISTA with only 6 layers, a NMSE equals to -24 dB can be reached. On the other hand, more than 3600 iterations of ISTA would be required to achieve this NMSE value.

• LISTA network generates estimates with lower NMSE value and less computational complexity (significantly fewer matrix-vector multiplications) than ISTA.

• With LISTA, the parameters are internally optimized during the training phase.

Therefore, the obtained results show that LISTA generates better estimate than ISTA. Furthermore, combining LISTA with one of the shrinkage function presented in Section 5.5, an estimate close to the OLS can be achieved using few layers of LISTA.

The above simulations consider that the training data and the signal of interest have similar characteristics. However, the signal to be estimated can have different characteristics compared to those of the training data used to training the network. In order to analyze the robustness of the network generated by LISTA, two different cases were simulated:

• Case 1: the signal to be estimated and the signals used during the training phase have different SNR values. It can be noticed that the performance decreases, as outside the zone near to SNR = 30 dB, the obtained NMSE values are not close to those produced by OLS. That being said, even if for SNR ≤ 20 dB, all shrinkage functions lead to similar performances, the functions η spl , η exp , and η pwl achieve better results than the traditional function for SNR ≥ 20 dB. As well as SNR, the sparsity of the signal to be estimated may not be fixed. As can be seen in Fig. 5.22, LISTA with η st has some degree of robustness when the sparsity varies.

However, this robustness clearly increase when one of the shrinkage functions proposed is used.

The results indicate that the choice of the shrinkage function is an important factor for the esti-

SPARSE SIGNAL ESTIMATION IMPROVEMENT TECHNIQUES

Performance Comparison

This section presents a performance comparison between some sparse recovery algorithms reported in the literature and the approaches proposed in this thesis. The algorithms and neural network analyzed here are:

• OLS: theoretical performance bound Oracle Least Square;

• MP: Matching Pursuit (see Section 3.3.1);

• OMP: Orthogonal Matching Pursuit (see Section 3.3.2);

• MPLS: Matching Pursuit based on Least Squares (see Section 5.1);

• LISTA s : Learned Iterative Shrinkage-Thresholding Algorithm with the traditional shrinkage function η st defined by (3.16) (see Section 4.2.1);

• LISTA pwl : Learned Iterative Shrinkage-Thresholding Algorithm with the piecewise linear shrinkage function η pwl defined by (5.30) (see Section 5.5);

• Tech. 1: Proposition to improve the LISTA performance (see Section 5.3);

• PNN s : Proposed Neural Network (Tech. 2) with the shrinkage function η st defined by (3.16) (see Section 5.4);

• PNN pwl : Proposed Neural Network (Tech. 2) with the piecewise linear shrinkage function η pwl defined by (5.30) (see Section 5.4).

They are evaluated in terms of NMSE described by (5.2), the percentage of non-zero taps positions correctly found (P c ) and the percentage of taps which had an improper attribution (P e ). The number of multiplications (N M ) is used as the parameter of the algorithm computational complexity.

Firstly the floating-point arithmetic implementation is considered (see Section 5.6.1). Then the estimation performances are analyzed using fixed-point arithmetic (see Section 5.6.2).

The system model is defined by (2.8), considering:

• N = 256.

• M = 128.

• A is i.i.d. Gaussian, with elements distributed N (0, M -1 ).

• h is Bernoulli-Gaussian, that is, its elements are i.i.d N (0, 1) with probability γ = 0.1 and the others are set to 0.

• SNR = 30 dB.

• N s = 10000.

• The training data sets used in the neural networks analyzed have D = 10000 pairs of elements.

• The testing phase of the neural networks analyzed have another sets with a size of 10000 pairs of elements.

• The Adam optimizer was used in the neural networks analyzed.

• α = 0.02 for Tech.1.

• τ = 0.2 for PNN s and PNN pwl . Fig. 5.24 shows the percentage of non-zero taps positions correctly found. It can be noticed that the greed algorithms require more N M to correctly found more than 80% of the non-zero tap positions. In contrast, LISTA s and LISTA pwl correctly found more than 80% of the non-zero tap positions faster than the others techniques, that is, with fewer N M . However, one problem of LISTA is that it attributes non-zero values to a lot of taps, so even if it finds a lot of nonzero tap positions, it also attributes small values to wrong taps. This can be noticed in Fig. 5.25 that provides the percentage of taps with an improper attribution. This characteristic of LISTA is more accentuated in LISTA pwl that assigns non-zero values to almost all taps as can be noticed in These results suggest that PNN pwl is the best technique to found the non-zero tap positions. This

Estimation Performance: Floating-point Arithmetic

Estimation Performance: Fixed-point Arithmetic

Sparse signal recovery on hardware is challenging since it consists of dot product operations and complex matrix inversion (depending on the sparse recovery algorithm chosen). A hardware implementation has to take into account its cost and its performance. In general, more hardware multipliers and more memory imply more power consumption. However, some applications have hardware constraints requiring low-power and low-cost signal processing operations targeting longer battery life or more compact physical devices.

One alternative is to reduce the number of bits used in the hardware implementation to represent the values that will be calculated. Processors designed for extremely low power consumption or very small size usually only provide multiplication instructions that are limited with respect to the bit size of the words [START_REF] Pyeatt | Modern Assembly Language Programming with the ARM Processor[END_REF]. However, this reduction often leads to a degradation of the algorithm performance. Therefore, this negative impact should be analyzed.

Floating-point arithmetic is complex and requires more area than fixed-point arithmetic increasing hardware complexity [START_REF] Kulkarni | A parallel and reconfigurable architecture for efficient OMP compressive sensing reconstruction[END_REF]. Moreover, fixed-point implementation reduces the amount of switching activity on wires and logic gates, leading to the reduction of power dissipation [START_REF] Kulkarni | Low overhead architectures for OMP compressive sensing reconstruction algorithm[END_REF].

Taking these into account, the algorithms evaluated here were implemented using fixed-point arithmetic. In this thesis, Qi. f is used to represent the quantization format where i is the amount of integer bits and f is the amount of fractional bits.

The residual vector b i of the OMP algorithm is always orthogonal to the columns that have already been selected. Therefore, theoretically, there will be no columns selected twice and the set of selected columns is increased through the iterations. However, when the OMP is implemented with limited data representation, there is an imperfect orthogonalization caused by inaccurate least square calculation. For this reason, a choice should be made when implementing it:

• OMP n : the implementation can be forced to always choose a new non-zero tap, that is, different from the ones selected in previous iterations keeping the original sense of orthogonality of the OMP.

• OMP r : the implementation allows the non-zero tap to be re-selected in others iterations considering that orthogonality is not really achieved. The MP, OMP and MPLS algorithms start considering that all taps have zero values. Throughout each iteration they increase or maintain the amount of non-zero taps. This can be seen in Therefore, it can be seen from Fig. 5.27 and Fig. 5.28 that depending on the amount of bits, the algorithm that has the best estimation performance for a small N M value varies. In other words, it would be better to choose the OMP algorithm to sparse signal estimation if 16-bits implementation is used. On the other hand, if 24-bits implementation is used, it would be better to choose the MPLS algorithm so it would reduce the computational complexity (N M < 6.5 × 10 6 ) and achieve a lower NMSE value. This difference in the estimation performance of 16-bits and 24-bits implementations occurs because with more bit accuracy (more bits), the fact that the MPLS algorithm finds the correct positions of the non-zero taps with fewer iterations than the OMP algorithm is a big advantage for the estimated signal calculation. In addition, as expected, increasing the number of bits improves the estimation performance of the algorithms, i.e., the achieved NMSE value decreases. the quantization noise imposed by bit limit precision. It is defined by (5.33) varying the number of fractional bits. The results are compared to the OLS (blue curve). It has the previous knowledge of the non-zero tap positions and calculates their non-zero coefficients with the floating-point least square solution. Therefore, these thresholds represent the optimal NMSE achievable limit (OLS) and the limit due to bit accuracy (B l ). It can be noticed that the MP, MPLS and OMP don't achieved the limit boundaries.

B l = 2 -2 f × N × N s ∑ ||h|| 2 2
(5.33) Sparse signal estimation using neural network has advantages when it is implemented in fixedpoint arithmetic. The neural network training does not necessarily have to be done in hardware, so floating-point arithmetic can be used to train the network. Once trained, the sparse signal estimation is done using the neural network with fixed-point arithmetic. The results of LISTA pwl are not presented here because more than 80% of taps had an improper attribution as can be seen in Fig. 5

Conclusion and Perspectives

This chapter presents some conclusions and perspectives of this thesis work.

Conclusions

This thesis dealt with sparse channel estimation and exploration of new approaches to sparse signals estimation. High-quality channel estimation is very important to a reliable communication system. Several channels can be considered sparse. This characteristic can be used to improve their estimation. The compressive sensing and its sparse recovery algorithms are used in several areas and they can be applied to sparse channel estimation reducing the cost and the complexity of the estimation as well as the required amount of measurements. The work performed during this thesis mainly focused two aspects: sparse recovery algorithms and neural networks based compressive sensing.

Starting from the state of the art, several sparse recovery algorithms were studied and analyzed in Chapter 3. A performance analysis suggested that these algorithms better estimate sparse signals. In other words, the sparser the signal is, the smaller the estimation error will be. In addition, the algorithms BCS and OMP presented the lowest NMSE values (see Section 3.4). This study led to the first contribution of this thesis: the proposition of a greed algorithm called Matching Pursuit based on Least Squares (MPLS) which combines the Matching Pursuit and the Least Square algorithms (see Section 5.1). The results showed that the MPLS algorithm offers a better tradeoff between estimation accuracy and computational cost than OMP algorithm, while producing similar results.

The study of these algorithms also led to the interest and study of the neural networks inspired by some of these algorithms, as discussed in Chapter 4. It resulted in other three contributions of this thesis presented in Sections 5.3, 5.4 and 5.5 to improve sparse signal recovery.

LISTA can be considered as one of the first neural network inspired by a sparse recovery algorithm. In this thesis, it is proposed to use the LISTA output to give a direction of the nonzero tap selection. The non-zero tap positions are chosen according to a threshold related to the biggest tap given by LISTA output. Then the signal estimate will be calculated by pseudoinversion process (see Section 5.3). The obtained results show that using this approach, the NMSE value can be reduced up to 5.9 dB comparing to the LISTA estimation performance.

In addition, a new neural network focused on finding the non-zero tap positions was proposed (see Section 5.4). The obtained results show that the proposed network is a good approach to sparse signal recovery reducing up to 10.8 dB the NMSE value compared to LISTA and achieving performance close to OLS. Furthermore, fewer layers are required to achieve good estimates leading to less time required for training phase and less matrix-vector multiplications required during the evaluation phase.

Moreover, other shrinkage functions are suggested to replace the traditional shrinkage function of LISTA. Their estimation performances are analyzed in Section 5.5. The obtained results indicate that the estimates generated by the LISTA network require fewer matrix-vector multiplications than existing algorithms with optimally tuned regularization parameters. Furthermore, choosing an adequate shrinkage function, the LISTA can achieve NMSE values close to the theoretical performance bound with a few layers.

The results of this thesis reinforce the suitability of neural network in sparse signal estimation as an alternative to the sparse recovery algorithms. The approaches developed in this work can be extended and used to sparse signal estimation in several domains such as those presented in Section 2.3.2.

Most of the works covered in this thesis were published in appropriate conferences and journal, and those publications are listed in Appendix A.

Perspectives

As an extension of this thesis, the points below can further improve this work:

• Regarding the sparse recovery algorithms, a lot of them assume that the signal's sparsity is known. However, in several applications this is not true. Thus, it is necessary to develop sparse recovery algorithms that do not need this information and that are able to be adaptive to time changes. One other approach is to develop a sparsity estimator such as the proposed in [START_REF] Salehi | Energyaware adaptive rate and resolution sampling of spectrally sparse signals leveraging VCMA-MTJ devices[END_REF].

• Although the use of neural network leads to performance improvements, it presents some challenges. The optimization algorithm, the loss function, and training strategies influence a lot the NN estimation performance. Therefore, they can be modified to try improve the sparse signal estimation performance.

• It should be interesting to explore the use of alternative functions f (x) in the proposed neural network, so as to their estimation performance impact.

• Another opportunity for future work would be to make the function η r (see (5.24)) of the proposed neural network variable according to the layer. For example, to use a η r1 function in the first layers and after to use a different η r2 function.

• The step proposed in Fig. 5.10 can be applied in other neural networks. For instance, to replace the first step "LISTA" for another neural network for example LAMP and to use the estimate given by LAMP as ĥ in Fig. 5.10.

• The obtained results show that characteristics (e.g. SNR or γ) of the training set must match with those of the signal to be estimated, otherwise it can lead to some degradation in terms of NMSE. However, sometimes these characteristics vary, so a better choice of the training set should be done. For example, use with different SNR to better estimate a signal with variable SNR. Some simulations should be done to find the best way to compose the training set.

• As several channels are more complex in reality than their mathematical models and change over time, general NN that dynamically adapts to varying channel conditions is desirable. Enfin, le signal est reconstruit par un algorithme d'acquisition comprimée [START_REF] Marques | A review of sparse recovery algorithms[END_REF]. Les réseaux de neurones abordés sont :

B.3 Algorithmes d'Acquisition Comprimée

• Learned Iterative Shrinkage-Thresholding Algorithm (LISTA) ;

• Learned Approximate Message Passing (LAMP) ;

• Deep l 0 -Regularized Encoder (Dl 0 RE) ;

• Learned Denoising-based Approximate Message Passing (LDAMP) ;

• Trainable ISTA (TISTA) ;

• Stein's Unbiased Risk Estimate based-Trainable Iterative Thresholding Algorithm (SURE-TISTA).

Dans [START_REF] Kamilov | Learning optimal nonlinearities for iterative thresholding algorithms[END_REF], les auteurs proposent d'utiliser les B-splines cubiques comme fonction de retrait dans LISTA. Alternativement, les auteurs de [START_REF] Mahapatra | Deep sparse coding using optimized linear expansion of thresholds[END_REF] Considérons Λ i l'ensemble d'index des colonnes les mieux alignées de A jusqu'à l'itération i, Λ i est actualisé selon les règles suivantes :

• Si k i / ∈ Λ i-1 , l'ensemble d'index est mis à jour en tant que Λ i = Λ i-1 ∪ k i .

• Autrement, Λ i = Λ i-1 .

Ensuite, la projection du vecteur résiduel dans cette direction est supprimée et un nouveau vecteur résiduel est calculé comme (B.3). La première étape consiste en l'implémentation de LISTA, qui produit l'estimation ĥ. La deuxième étape ("Selection") prend en compte α et ĥ pour produire le vecteur v . Cette étape vise à utiliser le seuil µ. Soit g le nombre de taps non nuls de ĥ, E la plus grande valeur absolue d'un composant de ĥ et α soit une valeur positive (µ = αE), les éléments du vecteur v sont calculés par : v (i) = 1, si ĥ(i) > µ v (i) = 0, si ĥ(i) ≤ µ (B.7)

b i = b i-1 -P a k i b i-1 = b i-1 - (a k i H b i-1 )a k i ||a k i ||
C'est-à-dire que cette étape génère un signal v avec j éléments 1 où j ≤ g ≤ N. Les positions de ces j éléments non nuls seront les mêmes positions des éléments non nuls de v.

Soit G(x) la matrice M × K composée uniquement de K colonnes de la matrice A corrélée aux positions du non-nul éléments de x. La fonction U(x) est définie par :

U(x) = G † (x)y = G T (x)(G(x)G T (x)) -1 y (B.8)
Enfin, l'étape "l 2 Optimization" calcule les éléments non nuls de v par U(v ). Ensuite, l'estimation v du signal fragmenté h est calculée en attribuant les valeurs du vecteur généré par U(v ) dans le positions i où v (i) = 1.

Le NMSE décrite par (5.2) est utilisé pour évaluer la proposition d'amélioration des performances de LISTA ("Tech. 1"). Le modèle du système est défini par (B.6). N = 120, M = 60, N s = 5000, SNR = 30 dB, A est i.i.d gaussien N (0, M -1 ). h est Bernoulli-Gaussian. Ses éléments sont i.i.d N (0, 1) avec probabilité γ = 0, 1 et les autres sont définis comme 0.

Les paramètres de LISTA ont été directement tirés de réalisations indépendantes des données d'apprentissage au cours de la phase d'apprentissage. Les ensembles de données d'apprentissage {(y d , h d )} D d=1 avec D = 10000 ont été utilisés. Un autre ensemble d'une taille de 10000 a été utilisé pour la phase de test. Il a été généré indépendamment des données d'apprentissage mais à partir de la même distribution. Au cours de la phase d'apprentissage, LISTA adapte les paramètres en minimisant la fonction de perte (B.9) à l'aide de l'optimiseur Adam [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF]. améliorer les performances de l'estimation (diminution de la valeur de NMSE) [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF].

Comme le montre la Fig. B.9, avec α = 0.02, la valeur de NMSE peut diminuer jusqu'à 5.9 dB par rapport à LISTA std . Cela se produit car, même si LISTA choisit les bons paramètres Θ, l'estimation ĥ donnée par LISTA a plus de elements non nuls que h, conduisant à de plus mauvaises valeurs NMSE. Par conséquent, après l'étape "Sélection", le nombre de positions des éléments non nuls diminue et l'étape "l 2 Optmization" calcule leurs valeurs à l'aide de l'algorithme LS, ce qui entraîne une valeur inférieure de NMSE. Après le réseau de neurones proposé, p est l'estimation des positions des éléments non nuls de ĥ. En d'autres termes, p(i) = 0 correspond aux taps de ĥ qui ont une valeur 0 et p(i) = 1 représente les taps de ĥ qui ont une valeur non nulle.

Les éléments non nuls de ĥ sont calculés via la solution des moindres carrés. En d'autres termes, les éléments non nuls de l'estimation ĥ du signal parcimonieux h sont calculés par U(p)

(voir (5.23)) et composent le vecteur u. Ensuite, l'estimation ĥ est calculée en attribuant les valeurs du vecteur u aux positions des éléments non nuls de p.

Les principales différences entre LISTA et le réseau de neurones proposé sont [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF] :

• Alors que LISTA estime directement ĥ, le réseau de neurones proposé estime les positions des éléments non nuls de ĥ.

• Pour estimer les positions des éléments non nuls, deux autres "étapes" sont introduites après la dernière couche du réseau (voir la Fig. 5.13).

• Les valeurs d'éléments de ĥ ne sont pas directement calculées par le réseau de neurones proposé. Ils sont calculés via la solution des moindres carrés basée sur la sortie du réseau de neurones proposé.

Les résultats montrent que le réseau de neurones proposé améliore les valeurs de NMSE par rapport à LISTA. En effet, en utilisant η r = η pwl la valeur de NMSE peut diminuer jusqu'à 10.

1 Introduction 1 . 1

 111 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Thesis Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Basic Concepts 2.1 Software Defined Radio (SDR) . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Sparse Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Compressive Sensing (CS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Basics on Compressive Sensing . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Application of Compressive Sensing . . . . . . . . . . . . . . . . . . . . 3 Sparse Recovery Algorithms 3.1 Convex Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Basis Pursuit (BP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 BP De-Noising (BPDN) / Least Absolute Shrinkage and Selection Operator (LASSO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3 Least Angle Regression (LARS) . . . . . . . . . . . . . . . . . . . . . . 3.1.4 The Dantzig Selector (DS) . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.5 Iterative Soft Thresholding (ISTA) . . . . . . . . . . . . . . . . . . . . . 3.1.6 Approximate Message Passing (AMP) . . . . . . . . . . . . . . . . . . . 3.1.7 Gradient Descent with Sparsification (GraDeS) . . . . . . . . . . . . . . 3.2 Non-Convex Optimization Techniques . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Bayesian Compressive Sensing (BCS) . . . . . . . . . . . . . . . . . . . 3.2.2 Focal Underdetermined System Solution (FOCUSS) . . . . . . . . . . .

2. 1

 1 Comparison between random and deterministic sensing. . . . . . . . . . . . . . . 3.1 Main parameters and calculations of Greedy Algorithms. . . . . . . . . . . . . . 3.2 Percentage of non-zero tap positions correctly found. . . . . . . . . . . . . . . . 4.1 Activation functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Comparison of the neural networks addressed in Section 4.2. . . . . . . . . . . . 5.1 Number of channels that found the correct positions of non-zero channel taps. . . 5.2 Number of layers required to achieve a given performance using "Tech. 1". . . . HELU Hard thrEsholding Linear Unit. HF High Frequency. HHS Heavy Hitters on Steroids. IBTMC Inter-Burst Translational Motion Compensation. IHT Iterative Hard Thresholding. IHTA Iterative Half Thresholding Algorithm. IoT Internet of Things. IRLS Iterative Reweighted Least Squares. ISAR Inverse Synthetic Aperture Radar. ISDB-T Integrated Services Digital Broadcasting-Terrestrial. ISTA Iterative Soft Thresholding. LAMP Learned Approximate Message Passing. LARS Least Angle Regression. LASSO Least Absolute Shrinkage and Selection Operator. LDAMP Learned Denoising-based Approximate Message Passing. LISTA Learned Iterative Shrinkage-Thresholding Algorithm. LS Least Square. LVAMP Learned Vector Approximate Message Passing. MAP Maximum a posteriori. MIMO Multiple-Input Multiple-Output. ML Maximum Likelihood. MMP Multipath Matching Pursuit.

n M × 1

 1 noise vector A M × N measurement matrix Ψ N × N basis matrix N length of the sparse signal h M length of the received signal y N L the number of layers of the neural network s signal's sparsity Λ i set of the indices chosen untill iteration i δ s the smallest number that achieves RIP N it number of iterations Chapter 1

Figure 1 . 2 -

 12 Figure 1.2 -Classification of channel estimation techniques.

Figure 1 . 3 -

 13 Figure 1.3 -Transmitted symbol vector with T training and D data symbols.

Fig. 2 .

 2 Fig. 2.1 shows a 200 samples length time-domain signal (Fig. 2.1a) representing 8 distinct sinusoids (Fig. 2.1b). This figure is an example of 8-sparse signal in frequency domain, that is, it can be seen in Fig. 2.1b that only 8 non-zero values exist among the 200 frequencies.

Figure 2 . 1 -

 21 Figure 2.1 -Samples of 8 sinusoids in (a) time and (b) frequency domains.

Figure 2 . 2 -

 22 Figure 2.2 -Compressive sensing main steps.

Figure 2 . 3 -

 23 Figure 2.3 -Representation of measurements used in compressive sensing.

Figure 2 . 4 -

 24 Figure 2.4 -Sparse signal estimation using the LS algorithm.

Figure 3 . 1 -

 31 Figure 3.1 -Classification of sparse recovery algorithms.

Figure 3 . 3 -

 33 Figure 3.3 -Greedy Algorithms Diagram.

Figure 3 . 4 -

 34 Figure 3.4 -Comparison between the OMP and the MMP algorithms (L = 2): (a) OMP (b) MMP.

Figure 3 . 5 -

 35 Figure 3.5 -Algorithms performances varying M for γ = 0.05.

Figure 3 . 6 -

 36 Figure 3.6 -Algorithms performances varying γ for M = 512.

Chapter 4 Deep

 4 Learning based Compressive SensingThis chapter explores some neural networks used to estimate sparse signals. Firstly, key concepts related to deep learning are introduced. Then, several neural network proposed in the literature are addressed. Some of them were inspired by sparse recovery algorithms presented in Chapter 3.

Figure 4 . 1 -

 41 Figure 4.1 -A neuron element of a neural network.

Figure 4 . 2 -Figure 4 . 4 -

 4244 Figure 4.2 -A fully connected feed-forward NN architecture.

Figure 4 . 5 -

 45 Figure 4.5 -Neural networks inspired by sparse recovery algorithms presented in this section.

4. 2 . 1

 21 Learned Iterative Shrinkage-Thresholding Algorithm (LISTA)Inspired by the Iterative Shrinkage-Thresholding Algorithm (ISTA -see Section 3.1.5), a neural network architecture called Learned Iterative Shrinkage-Thresholding Algorithm (LISTA) was proposed in[START_REF] Gregor | Learning fast approximations of sparse coding[END_REF] to sparse signal estimation. Fig.4.6 shows, as an example, the neural network LISTA with three layers.

Figure 4 . 6 -|| 2 ( 4 . 3 )

 46243 Figure 4.6 -Example of LISTA with 3 layers.

(4. 4 )Figure 4 . 7 -

 447 Figure 4.7 -One layer of LISTA network.

Fig. 4 .

 4 Fig. 4.8 illustrates one layer of LAMP. The parameters α i and the N × M matrices C i are learned during the training phase from the training data {(y d , h d )} D d=1 .In each layer two matrixvector multiplications are performed (with C i and A). Therefore, the computational and memory

Figure 4 . 8 -

 48 Figure 4.8 -One layer of the LAMP network.

4. 2 . 3 Fig. 4 .Figure 4 . 9 -

 23449 Fig.4.9 illustrates the Deep l 0 -Regularized Encoder proposed in[START_REF] Wang | Learning deep l 0 encoders[END_REF] where ĥi is the output of the layer i. The N × M matrix C, the N × N matrix S, and θ are shared among both stages and are learned during the training phase. In this thesis, this neural network is also called "Dl 0 RE".

Fig. 4 .Figure 4 . 10 -

 4410 Fig.4.10 illustrates one layer of the LDAMP neural network[START_REF] Metzler | Learned D-AMP: Principled neural network based compressive image recovery[END_REF]. The Denoiser block D(.) is composed by a Denoising Convolutional Neural Network (DnCNN). The DnCNN neural network has 16 to 20 convolutional layers. The first layer uses 64 different 3x3xc filters (where c is the number of color channels) and is followed by ReLU[START_REF] Metzler | Learned D-AMP: Principled neural network based compressive image recovery[END_REF]. The next 14 to 18 convolutional layers each use 64 different 3x3x64 filters which are each followed by batch-normalization[START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF] and a

Figure 4 . 11 -

 411 Figure 4.11 -One layer of the TISTA network.

Chapter 5 Sparse

 5 Signal Estimation Improvement Techniques This chapter presents the sparse signal estimation improvement techniques proposed in this thesis. In Section 5.1 a greedy algorithm called Matching Pursuit based on Least Squares (MPLS) is explained. The algorithms LS, MP, OMP, and MPLS are used to estimate two different Wideband HF channels in Section 5.2. Then, an alternative to improve LISTA estimation performance is addressed in Section 5.3. A new neural network to sparse signal estimation is discussed in Section 5.4. Section 5.5 suggests some alternative shrinkage functions to replace the traditional shrinkage function used in LISTA. Finally, Section 5.6 analyzes the performance of all techniques proposed in this thesis.

Fig. 5 .

 5 Fig. 5.1 presents the LS, MP, MPLS, OMP and OLS algorithms performances in terms of MSD versus channel sparsity for M = 60. Let N it be the number of iterations (stopping criterion), in Fig. 5.1, the continuous lines represent the simulations with N it = 2S, while the broken lines denote the simulations with N it = S.

Figure 5 . 1 -

 51 Figure 5.1 -MSD vs Sparsity for SNR = 10dB, M = 60.

Fig. 5 .

 5 Fig. 5.2 considers M = 120, i. e., the same length of the channel. The stopping criterion is the number of iterations equivalent to the number of non-zero channel taps (i.e., N it = S). Comparing Fig. 5.1 and Fig. 5.2, it can be seen that as M increases, the MSD of the algorithms decreases.

Figure 5 . 2 -

 52 Figure 5.2 -MSD vs Sparsity for SNR = 10dB, stopping criterion N it = S, M = 120.

Figure 5 . 4 -

 54 Figure 5.4 -Delay Power Profile.

Fig. 5 .

 5 Fig. 5.4 specifies the DPP, where σ τ is the delay spread, σ c is the rise time, A is the maximum value of the DPP. Let τ be the delay variable, ∆ controls the width, τ c controls the delay offset, α

  For example, Fig. 5.5 shows a wideband HF channel impulse response with 4 propagation paths and delay spread σ τ = 100 µs. The symbol rate is 19 200 symbol/s, that is used for a bandwidth of 24 kHz according to the Appendix D of the MIL-STD-188-110C [217].

  denotes the time-domain discrete wideband HF channel vector with N > M taps and n is the Additive White Gaussian Noise (AWGN). A stands for the M × N measurement matrix. The ith column of A is denoted a i . A is a Toeplitz matrix determined by the QPSK training symbols. Two different wideband HF channels are considered and the Mean-Square Deviation (MSD) described by (5.10) is used to evaluate the algorithms in terms of the quantity of the acquired measurement (M) and the number of iterations (N it ), where N s is the number of channel simulations. For these simulations, N = 127 and SNR = 20 dB.

Figure 5 . 5 -

 55 Figure 5.5 -Example of a wideband HF channel with 4 propagation paths.

Figure 5 . 6 -

 56 Figure 5.6 -MSD vs N it for M = 40 and wideband HF Channel A.

Fig. 5 .

 5 Fig. 5.8 presents MSD values varying the quantity of the acquired measurement for S = 4. It

Figure 5 . 7 -Figure 5 . 8 -

 5758 Figure 5.7 -MSD vs N it for M = 40 and wideband HF Channel B.

Figure 5 . 9 -

 59 Figure 5.9 -Example of a sparse signal h and its estimate ĥ given by N L = 20 layers of LISTA.

Figure 5 . 10 -

 510 Figure 5.10 -General schema of "Tech. 1".

  The parameters of LISTA were directly learned from independent realizations of the training data during the training phase. Training data sets {(y d , h d )} D d=1 with D = 10000 were used. Another set with a size of 10000 was used for the testing phase. It was generated independently of the training data but from the same distribution. During the training phase, LISTA adapts the parameters minimizing the loss function (4.

Figure 5 . 11 -

 511 Figure 5.11 -Estimation performance for different values of α using "Tech. 1".

Figure 5 . 13 -

 513 Figure 5.13 -Proposed neural network with N L layers.

Figure 5 . 15 -

 515 Figure 5.15 -Percentage of taps that had an improper attribution with the proposed neural network (Tech. 2).

Figure 5 .

 5 Figure 5.16 -NMSE × N L using "Tech. 1" and "Tech. 2".

Fig. 5 .Figure 5 . 17 -

 5517 Fig. 5.18.a. Recently, cubic B-splines shrinkage function has been used in LISTA with several parameters spread uniformly over the dynamic range of the signal to improve the estimation qual-

Figure 5 . 18 -

 518 Figure 5.18 -Shrinkage functions for different parameters.

Fig. 5 .

 5 Fig. 5.19 presents the ISTA estimation performance for different values of the parameters β and λ [229].

Figure 5 . 19 -

 519 Figure 5.19 -ISTA estimation performance for different β and λ values.

Fig. 5 .

 5 Fig. 5.20 presents the LISTA estimation performance in terms of NMSE value considering the traditional shrinkage function (3.16) and the functions described in Section 5.5 for different numbers of layers [229]. The parameters of the shrinkage functions were learned directly from independent realizations of the training data during the training phase.

Figure 5 . 20 -

 520 Figure 5.20 -LISTA estimation performance according to the number of layers.

Fig. 5 .

 5 Fig. 5.21 shows LISTA behaviour varying the SNR value of the signal to be estimated. The network has N L = 20 and the training data has SNR = 30 dB [229].

  Figure 5.21 -LISTA estimation performance varying the SNR of the signal to be estimated.

Fig. 5 .

 5 Fig. 5.22 shows the LISTA estimation performance varying the γ of the signal to be estimated. N L = 20 and the training data has γ = 0.1 [229]. As expected, when the signal to be estimated is less sparse (γ > 0.1) than the signals used in the training data (γ = 0.1), the NMSE values achieved by LISTA dissociate themselves from the NMSE of the OLS. However, it should be highlighted that the use of one of the shrinkage functions presented in Section 5.5 instead of the traditional shrinkage function (3.16) leads to better NMSE values.

  Figure 5.22 -LISTA estimation performance varying the γ of the signal to be estimated.

Fig. 5 .

 5 Fig. 5.20 and Fig. 5.21 point out that using a training data with a determined value of SNR and γ to estimate a signal with different values for these parameters leads to decreased LISTA estimation performance. To improve the LISTA performance, in addition to change the shrinkage function to one of the presented in Section 5.5, the training data could be modified.

Fig. 5 .

 5 Fig.5.23 presents the estimation performances for floating-point arithmetic in terms of number of multiplications (N M ). The results indicate that using neural network for estimating the sparse signal leads to better estimation performance (lower NMSE value) than using one of the greedy algorithm analyzed (MP, MPLS, and OMP). Indeed, the NMSE values achieved by the greedy algorithms are very far from the value reached by the OLS. Moreover, it can be seen in Fig.5.23 that LISTA pwl , Tech. 1, PNN s and PNN pwl improve the estimation performance compared to LISTA s . In addition, LISTA pwl and PNN pwl are the ones which achieve results closer to the one of the theoretical performance bound OLS. As η pwl has more parameters than η s , this has an important influence on the estimation performance of LISTA and PNN as can be noticed when comparing the results of LISTA s /LISTA pwl and PNN s /PNN pwl .

Fig. 5 .

 5 Fig. 5.24 and Fig. 5.25. Even if it has a big P e , it doesn't influence a lot the NMSE because the values attributed to the taps are close to zero. However, LISTA pwl is not appropriated to be use if the knowledge of the non-zero tap positions is important. Fig. 5.25 shows that Tech. 1, PNN s and PNN pwl have lower P e than LISTA s and LISTA pwl . Indeed, P e < 2% can be achieved with N M = 3 × 10 5 , N M = 5 × 10 5 , and N M = 13 × 10 5 using PNN pwl , PNN s , and Tech. 1, respectively.

Figure 5 . 23 -

 523 Figure 5.23 -Estimation performance for floating-point arithmetic in terms of number of multiplications (N M ).

Figure 5 . 24 -

 524 Figure 5.24 -Percentage of non-zero taps positions correctly found (P c ).

Figure 5 . 25 -

 525 Figure 5.25 -Percentage of taps which had an improper attribution (P e ).

Fig. 5 .

 5 Fig.5.[START_REF] Huang | An improved compressed sensing reconstruction algorithm used in sparse channel estimation[END_REF] shows the estimation performance in terms of NMSE varying the number of multiplication operation (N M ) considering the two alternatives of OMP implementation for Q8.8. It can be seen that when the non-zero taps can not be selected twice (OMP n ) the NMSE value is bigger than the OMP r case. It occurs because OMP n starts selecting wrong non-zero taps faster than OMP r , that is, with less iterations. Therefore, increasing the error estimation.

Figure 5 . 26 -

 526 Figure 5.26 -OMP n and OMP r estimation performances for Q8.8 (16 bits).

Fig. 5 .Figure 5 .

 55 Fig. 5.27 and Fig. 5.28 present the estimation performances of the MP, OMP and MPLS algorithms considering 16-bits implementation (Q8.8) and 24-bits implementation (Q8.16), respectively. Each point in the curves represents one iteration of the algorithm. It can be noticed thatfor the same quantity of multiplication operation (N M ) the OMP algorithm did less iteration (there are less points in the green curves than in the other curves). This occurs because each iteration of the OMP algorithm solves the least square problem which consumes a lot of multiplication operations. Indeed, as iteration order goes up, the OMP algorithm computational complexity of the iteration increases due to the expansion of the matrix which has to pass by the pseudo-inversion process. On the other hand, the MP algorithm has the simplest iteration calculations leading to more iterations (many blue points in the figures) for a same N M value.

Figure 5 . 28 -

 528 Figure 5.28 -MP, OMP and MPLS estimation performances for Q8.16 (24 bits).

Fig. 5 .

 5 Fig. 5.27 and Fig. 5.28. Initially the value of the NMSE decreases with the increase of N M . This is because the algorithms find the positions of the taps that have non-zero values and assign values to these taps. However, as the number of iterations increases, the algorithms start to assign nonzero values to taps that should have zero values, so the NMSE increases, i.e., the estimation error increases. For Q8.8 (Fig. 5.27) the algorithms were interrupted after increasing the NMSE values as the number of iterations increased.Considering the 16-bit implementation (Q8.8 -Fig.5.27), the OMP algorithm presents the best performance in terms of achieving lower NMSE for the same value of N M when compared to the MP and the MPLS algorithms for N M < 6.5 × 10 6 . On the other hand, for the 24-bit implementation (Q8.16 -Fig.5.28), the MPLS algorithm has the best performance (lowest NMSE value) for N M < 6.5 × 10 6 . If more multiplication operations are allowed then the OMP achieves better performance (lowest NMSE). Indeed, Fig.5.29 shows the minimum NMSE value achieved by the MP, OMP and MPLS algorithms for 24-bits implementation. As said before, each MPLS and MP iteration consumes fewer multiplication operations than one OMP iteration. Thus, it is possible to find the non-zero tap positions faster with the MP and MPLS algorithms and thus estimate the sparse signal faster than the OMP algorithm, leading to a lower NMSE value for a lower N M .

Figure 5 . 29 -

 529 Figure 5.29 -Minimum NMSE value for 24 bits (Q8.16).

Fig. 5 .

 5 Fig.5.[START_REF] Marques | A review of sparse recovery algorithms[END_REF] shows the percentage of non-zero taps positions correctly found according to the number of multiplication operations performed. The MPLS algorithm is not represented here because it finds the positions in the same way as the MP algorithm, the difference between these algorithms lies in the calculation of the non-zero tap values and not in the way to determine their positions. It can be seen in this figure that with 16-bits implementation, for the same value of N M , the OMP finds more correct positions, which contributes to the result presented in Fig.5.27.On the other hand, with 24-bits implementation (see Fig.5.30.b), the MP finds much more correct non-zero tap positions, quickly reaching more than 80% of non-zero tap positions. These positions are the same as those found by the MPLS algorithm. This result reinforces the good performance achieved by the MP and MPLS algorithms when compared to the OMP in Fig.5.28.

Fig. 5 .

 5 Fig. 5.31 presents the minimum NMSE value achieved for each algorithm considering 8 fractional bits (Q8.8) and 16 fractional bits (Q8.16) implementations. It is worth highlight that these minimums are achieved considering different computational complexities, i. e., different N M values for each algorithm (see Fig. 5.27 and Fig. 5.28). In addition, Fig. 5.31 shows in the rose line

Figure 5 . 30 -

 530 Figure 5.30 -Percentage of non-zero taps positions correctly found using the MP and OMP algorithms.

Fig. 5 .Figure 5 . 31 -

 5531 Fig. 5.32 shows the estimation performance, in terms of NMSE, for LISTA s , LISTA pwl , Tech. 1, PNN s , and PNN pwl considering Q8.8, Q8.16 and floating-point arithmetic (represented as f , for example LISTA s f means the float implementation of LISTA s ) implementations. The results presented in Fig. 5.23 are showed in Fig. 5.32 to facilitate the comparison. The Q8.16 implementationwell represents the floating-point arithmetic suggesting that using 16 bits for the fractional part is adequate. On the other hand, using 8 bits in the fractional part (Q8.8) decreases the estimation performance in all techniques. This decrease is bigger using Tech. 1, PNN s or PNN pwl than using

Fig. 5 .

 5 Fig. 5.33 presents the percentage of non-zero taps positions correctly found (P c ) using LISTA s , LISTA pwl , Tech. 1, PNN s , and PNN pwl considering Q8.8, Q8.16 and floating-point arithmetic implementations. The results presented in Fig. 5.24 are showed in Fig. 5.33 to facilitate the comparison. Tech. 1 provides the biggest difference when the implementation is changed from Q8.8 to Q8.16. For the other techniques, using Q8.8, the P c value doesn't decrease a lot. LISTA s , LISTA pwl , PNN s , and PNN pwl achieve more than 80% of non-zero tap positions correctly found with N M < 4 × 10 5 while the MP algorithm achieves it only with N M = 8.88 × 10 5 (see Fig. 5.30b).

Fig. 5 .

 5 Fig. 5.34 gives the percentage of taps which had an improper attribution (P e ) using LISTA s , Tech. 1, PNN s , and PNN pwl considering Q8.8, Q8.16 and floating-point arithmetic implementations. The results presented in Fig. 5.25 are showed in Fig. 5.34 to facilitate the comparison.

Figure 5 . 32 -Figure 5 . 33 -

 532533 Figure 5.32 -Estimation Performance for Q8.8, Q8.16 and floating-point arithmetic using: (a) LISTA s (b) LISTA pwl (c) Tech. 1 (d) PNN s (e) PNN pwl .

Figure 5 . 34 -

 534 Figure 5.34 -Percentage of taps which had an improper attribution (P e ) for Q8.8, Q8.16 and floating-point arithmetic using: (a) LISTA s (b) Tech. 1 (c) PNN s (d) PNN pwl .

LaFIGURE B. 4 -

 4 FIGURE B.4 -Échantillons de 8 sinusoides dans le domaine (a) temporel et (b) fréquentiel.

  modélisent la fonction d'activation non linéaire en utilisant une expansion linéaire des seuils. Dans cette thèse, d'autres fonctions d'activation à utiliser dans LISTA sont analysées dans la Section 5.5. L'étude de LISTA a abouti à la proposition de deux alternatives pour améliorer ses performances d'estimation. La première consiste à utiliser l'estimation de LISTA comme premier résultat pour estimer les positions des éléments non nuls d'un signal parcimonieux, puis de calculer leurs valeurs par un processus de pseudo-inversion (voir la Section 5.3). La seconde consiste à remplacer la fonction η st utilisée dans LISTA par d'autres fonctions (voir la Section 5.5). En outre, l'étude des réseaux de neurones abordé dans ce chapitre a motivé la proposition d'un nouveau réseau de neurones présentée dans la Section 5.4. B.5 Techniques d'Amélioration de l'Estimation de Signaux Parcimonieux Cette section présente les techniques d'amélioration de l'estimation de signal parcimonieux proposées dans cette thèse. Dans la Section 5.1, un algorithme glouton appelé Matching Pursuit based on Least Squares (MPLS) est expliqué. Les algorithmes LS, MP, OMP et MPLS sont utilisés pour estimer deux canaux large bande HF dans la Section 5.2. Ensuite, une alternative pour améliorer les performances d'estimation de LISTA est abordée dans la Section 5.3. Un nouveau réseau de neurones pour l'estimation de signaux parcimonieux est présenté dans la Section 5.4. La Section 5.5 propose des fonctions alternatives pour remplacer la fonction traditionnelle utilisée dans LISTA. Enfin, la Section 5.6 analyse les performances de toutes les techniques proposées dans cette thèse.Matching Pursuit based on Least Squares (MPLS) L'algorithme MPLS s'appuie sur l'algorithme MP pour rechercher les positions des éléments non nuls. Comme pour l'algorithme MP, chaque itération de l'algorithme MPLS consiste à rechercher la colonne a k i ∈ A qui s'aligne le mieux avec le résidu vector b i-1 (b 0 = y) et la sélection est effectuée en fonction de :k i = arg max l |a l H b i-1 |, l = 1, 2, ...., N (B.2)La différence entre les algorithmes MP et MPLS réside dans la manière dont les valeurs affectées aux éléments du signal non nuls sont calculées. L'algorithme MP estime le signal sous forme de valeurs de projection, tandis que l'algorithme MPLS effectue cette estimation via l'algorithme LS à la fin de l'algorithme.

2 2(B. 3 ) 2 (FIGURE B. 8 -

 2328 FIGURE B.7 -MSD vs Parcimonie pour SNR = 10dB, M = 60.

|| 2 (B. 9 )

 29 ĥT (y d ; Θ)h d || 2 La Fig. B.9 présente le NMSE obtenu en fonction du nombre de couches N L de LISTA. Comme prévu, l'augmentation du nombre de couches entraîne la diminution de la valeur de NMSE. De plus, sur la Fig. B.9, on peut constater qu'en utilisant les étapes proposées à la Fig. B.8, on peut

FIGURE B. 9 -FIGURE B. 10 - 2 (B. 11 )θ 1 sgn

 9102111 FIGURE B.9 -Estimation de la performance de "Tech. 1"avec différentes valeurs de α.

15 ) 2 3 -|z| 2 + |z| 3 2 , 1 1 6 ( 2 •

 1522162 8 dB par rapport à LISTA std et les résultats obtenus sont proches de OLS. D'autre part, lorsque η r = η st , Tech. 2 obtient des résultats similaires en termes de NMSE par rapport à celui obtenu avec Tech. 1.De plus, l'impact de la variation statistique du signal parcimonieux utilisé pendant la phase d'apprentissage et la phase d'évaluation est analysé.Fonctions alternatives pour LISTA Cette section explore les fonctions alternatives pour remplacer la fonction traditionnelle η st utilisée dans LISTA. L'objectif est d'analyser leur impact en termes de qualité d'estimation. Trois fonctions contrôlées par un petit nombre de paramètres sont prises en compte ici : Exponential (η exp ) : Soit θ = {θ 1 , θ 2 , θ 3 }, la fonction exponentielle est définie par[START_REF] Guo | Near optimal compressed sensing without priors: Parametric sure approximate message passing[END_REF] :η exp (x; θ) = θ 2 x + θ 3 xexp -Piecewise Linear (η pwl ) : Soit θ = {θ 1 , θ 2 , θ 3 , θ 4 , θ 5 }, cette fonction a cinq segments[START_REF] Guo | Near optimal compressed sensing without priors: Parametric sure approximate message passing[END_REF] :η pwl (x; θ) = si |x| ≤ θ 1 sgn(x)[θ 4 (|x|θ 1 ) + θ 3 θ 1 ], si θ 1 < |x| ≤ θ 2 sgn(x)[θ 5 (|x|θ 2 ) + θ 4 (θ 2θ 1 ) + θ 3 θ 1 ], si θ 2 < |x| (B.16)Spline (η spl ) : La fonction spline est définie par :η spl (x; θ) = θ 2 x + θ 3 xβ x θ 1 (B.17) où θ = {θ 1 , θ 2 , θ 3 } et β est la fonction cubic B-spline [228] : si 0 ≤ |z| ≤ -|z|) 3 , si 1 ≤ |z| ≤ 2 Les valeurs de NMSE obtenues par LISTA avec les fonctions piecewise linear, exponential, et spline sont meilleures que celles obtenues par LISTA avec la fonction traditionnelle η st . • L'utilisation de fonctions piecewise linear, exponential, et spline conduit à une diminution de la valeur de NMSE allant jusqu'à 9 dB par rapport à la fonction de réduction classique. • L'utilisation d'une des fonctions présentées dans la Section 5.5 permet à LISTA d'obtenir des performances proches de OLS dans un nombre raisonnable de couches. De plus, la performance d'estimation est analysée lorsque le signal à estimer a des caractéristiques différentes de celles des données d'apprentissage utilisées pour entraîner le réseau. Deux faut moins de couches pour obtenir de bonnes estimations, ce qui réduit le temps nécessaire à la phase de formation et réduit le nombre de multiplications matrice-vecteur nécessaires pendant la phase d'évaluation. Par ailleurs, d'autres fonctions de retrait sont proposées pour remplacer la fonction de retrait traditionnelle de LISTA. Leurs performances d'estimation sont analysées dans la Section 5.5. Les résultats obtenus indiquent que les estimations générées par le réseau LISTA nécessitent moins de multiplications matrice-vecteur que les algorithmes existants dotés de paramètres de régularisation optimisés. De plus, en choisissant une fonction de retrait adéquate, LISTA peut atteindre des valeurs de NMSE proches des performances théoriques liées à quelques couches. Les résultats de cette thèse renforcent l'adéquation du réseau de neurones à l'estimation de signaux parcimonieux comme alternative aux algorithmes d'acquisition comprimée. Les approches développées dans ce travail peuvent être étendues et utilisées pour l'estimation de signaux parcimonieux dans plusieurs domaines tels que ceux présentés dans la Section 2.3.2. La plupart des travaux couverts par cette thèse ont été publiés dans des conférences et un journal du domaine. Ces publications sont répertoriées dans l'annexe A.

  MMSE Minimum Mean Squared Error. SpAdOMP Sparse Adaptive Orthogonal Matching Pursuit. SURE-AMP Stein's Unbiased Risk Estimate Approximate Message Passing. SURE-TISTA Stein's Unbiased Risk Estimate based-Trainable Iterative Thresholding Algorithm.

	RVM Relevance Vector Machine.
	MP Matching Pursuit. SBL Sparse Bayesian Learning.
	MPLS Matching Pursuit based on Least Squares. SCA Software Communications Architecture.
	MRI Magnetic Resonance Imaging. SDR Software Defined Radio.
	MSD Mean-Square Deviation. SGD Stochastic Gradient Descent.
	NMSE Normalized Mean Squared Error. SGP Stochastic Gradient Pursuit.
	NN Neural Network. SLSMP Sequential Least Squares Matching Pursuit.
	NVIS Near Vertical Incidence Skywave. SNR Signal-to-noise ratio.
	OAMP Orthogonal Approximate Message Passing. SoC System on Chip.
	OLS Oracle Least Square. SP Subspace Pursuit.
	OMP Orthogonal Matching Pursuit.
	OTH Over-the-Horizon. SpaRSA Sparse Reconstruction by Separable Approximation.
	PAM Pulse Amplitude Modulation. StOMP Stagewise Orthogonal Matching Pursuit.
	PNN Proposed Neural Network.
	PSNR Peak Signal to Noise Ratio.
	QPSK Quadrature Phase Shift Keying. TISTA Trainable ISTA.
	TOMP Tree-based Orthogonal Matching Pursuit.
	ReLU Rectified Linear Unit.
	TSMP Tree Search Matching Pursuit.
	RF Radio Frequency.
	RIC Restricted Isometry Constant. VAMP Vector Approximate Message Passing.
	RIP Restricted Isometry Property. WISTA Weighted Iterative Shrinkage Thresholding Algorithm.
	RNN Recurrent Neural Network.
	ROMP Regularized OMP.

WSN Wireless Sensors Network.

Table 2 .

 2 1 -Comparison between random and deterministic sensing.

	Random Sensing	Deterministic Sensing
	Outside the mainstream of signal Aligned with the mainstream
	processing: worst case	of signal processing: average
	signal processing	case signal processing
	Less efficient recovery time	More efficient recovery time
	No explicit constructions	Explicit constructions
	Larger storage	Efficient storage
	Looser recovery bounds	Tighter recovery bounds

  Step 5: Stop the algorithm if the stopping condition is achieved (||b i || 2 ≤ ε 1 ). Otherwise, set i = i + 1 and return to Step 2.

Table 3 .

 3 2 -Percentage of non-zero tap positions correctly found.

	Algorithm	γ = 0.05 M = 200 M = 400	γ = 0.1 γ = 0.2 M = 512
	AMP	81.7%	98.4%	97.7% 88.5%
	FISTA	-	98.5%	98.2% 89.5%
	BCS	93.9%	97.0%	95.8% 91.9%
	OMP	92.1%	96.7%	95.8% 92.9%
	MP	67.6%	96.8%	96.2% 70.1%

Table 4 .

 4 1 -Activation functions.

	Name	σ(x)
	ReLU sigmoid softmax tanh(x)	max(0, x) 1 1+e -x e x i ∑ i e x i e x -e -x e x +e -x

Table 4 .

 4 2 presents a comparison between some neural networks addressed in Section 4.2. In this table, Θ represents the set of parameters which are learned during the training phase, M c is the memory complexity, MV is the number of matrix-vector multiplications performed in each layer, C c is the computational complexity, and σ represents the activation function. The function

	η in LAMP depends on the application (see Section 4.2.2). The LDAMP (see Section 4.2.4) is not

presented in this table because its memory and computational complexity depend on the DnCNN chosen.

It can be notice that the quantity of learned parameters required in TISTA and SURE-TISTA is

Table 4 .

 4 2 -Comparison of the neural networks addressed in Section 4.2. related to the number of layers N L while the number of learned parameters required in LISTA, LAMP and Dl 0 RE also depends on the values of M and N. Therefore, the number of learnable variables for TISTA and SURE-TISTA is much smaller than those of LISTA, LAMP and Dl 0 RE.

	Neural Network		Θ	M c	MV	C c	σ
	LISTA (Fig. 4.6) LISTA (Fig. 4.7) LAMP (Fig. 4.8) Dl 0 RE (Fig. 4.9) TISTA (Fig. 4.11) SURE-TISTA (Fig. 4.12)	C 1	C N×M , S N×N , λ 1 , . . . , λ N L C N×M , G M×N , λ 1 , . . . , λ N L N×M , . . . , C N L N×M , α 1 , . . . , α N L C N×M , S N×N , θ γ 1 , . . . , γ N L λ 1 , . . . , λ N L	≈ N 2 + MN ≈ 2MN ≈ N L MN ≈ N 2 + MN ≈ 2MN ≈ 2MN	1 2 2 1 2 2	η st (3.16) ≈ 2N L MN η st (3.16) ≈ N L N 2 η ≈ 2N L MN η H (4.9) ≈ N L N 2 η MMSE ≈ 2N L MN ≈ 2N L MN I (4.22)

only It significantly reduces the training complexity of TISTA and SURE-TISTA. If N > 2M, the computational complexity of LISTA (for the representation in Fig. 4.6) and Dl 0 RE is bigger than those of LISTA (for the representation in Fig. 4.7), LAMP, TISTA, and SURE-TISTA. Regarding to the memory complexity, LAMP can have the biggest one compared to the others NN presented in Table 4.2. It occurs because the memory complexity of LAMP also depends on N L while the others are only related to M and N values.

Table 5 .

 5 1 -Number of channels that found the correct positions of non-zero channel taps.

		5 correct positions	6 correct positions
	SC	MP/MPLS OMP MP/MPLS OMP
	N it = S	499	480	4484	4503
	N it = 2S	401	386	4589	4605

  .[START_REF] Cotter | Sparse channel estimation via matching pursuit with application to equalization[END_REF]. It can be noticed that PNN pwl leads to the lowest P e . This occurs because PNN is focused on finding the non-zero tap positions, so the neural network is trained for that, resulting in better performance than if LISTA is used.These results show that the performance of the techniques varies when the number of bit used in the fractional part changes. From these simulation, LISTA s is the technique that achieves better results for Q8.8 while for Q8.16 the PNN pwl leads to lowest percentage of taps with improper attribution and to good NMSE values.

		0					LISTA sf				0	LISTA pwlf
	NMSE (dB)	-20 -10					Q8.8 Q8.16				NMSE (dB)	-30 -20 -10	Q8.8 Q8.16
		-30	0	2	4	6	8 10 12			0	2	4	6	8 10 12
					N M (×10 5 )				N M (×10 5 )
						(a) LISTA s				(b) LISTA pwl
												Tech. 1 f
							NMSE (dB)	-20 -10 0				Q8.8 Q8.16
								-30
								0	2	4	6	8 10 12
										N M (×10 5 )
											(c) Tech. 1
		0						PNN sf				0	PNN pwlf
	NMSE (dB)	-20 -10						Q8.8 Q8.16				NMSE (dB)	-20 -10	Q8.8 Q8.16
		-30										-30
			0	2	4	6	8 10 12			0	2	4	6	8 10 12
					N M (×10 5 )				N M (×10 5 )
						(d) PNN s					(e) PNN pwl

  Eléments d'un système de communication. mis peuvent être récupérés sur le récepteur. Pour ce faire, plusieurs techniques d'estimation de canal ont été développées afin de fournir le CSI. En général, ces techniques peuvent être classées en trois catégories, comme illustré dans la Fig. B.2 [4]. De plus, dans des canaux variant dans le temps, la séquence d'apprentissage doit être transmise périodiquement, ce qui entraîne une perte supplémentaire du débit du canal. Par conséquent, il est intéressant de réduire la quantité requise de symboles d'apprentissage tout en conservant une précision d'estimation suffisante. Pour ce faire, la caractéristique du canal peut être utilisée pour améliorer les performances de son estimateur.La longueur d'un canal parcimonieux échantillonné peut atteindre des centaines d'intervalles de symboles, bien que la majorité des taps du canal échantillonné aient une valeur proche de zéro.La parcimonie du canal est définie comme le nombre de éléments non nuls du canal[START_REF] Berger | Application of compressive sensing to sparse channel estimation[END_REF][START_REF] Choi | Compressed sensing for wireless communications: Useful tips and tricks[END_REF]. Le grand avantage de CS est qu'il permet de numériser uniquement les informations du signal pertinentes à un taux d'échantillonnage beaucoup plus bas que le taux de Nyquist, de sorte que le signal numérisé est déjà 'estimation de canal peut être formulée comme un problème d'optimisation pouvant être résolu en utilisant des algorithmes numériques qui affinent sa solution de manière itérative. En règle générale, dans l'estimation du canal, une solution précise doit être trouvée avec un petit nombre d'itérations. De plus, ces algorithmes nécessitent des ajustements de paramètres qui, s'ils ne sont pas bien choisis, peuvent réduire les performances de l'algorithme.Le forum SDR définit un SDR comme "une radio dans laquelle certaines ou toutes les fonctions de la couche physique sont définies par le logiciel"[START_REF] Forum | What is software defined radio?[END_REF]. En d'autres termes, un SDR est une radio implémentée avec un matériel générique qui peut être programmé pour transmettre et recevoir une variété de formes d'onde (waveform).Signaux Parcimonieux Des signaux parcimonieux peuvent être trouvés dans plusieurs domaines[START_REF] Bruckstein | From sparse solutions of systems of equations to sparse modeling of signals and images[END_REF]. Par exemple, la plupart des images et des signaux audio présentent une décomposition parcimonieuse sur une base d'ondelettes et de fréquences-temps, respectivement. Ces signaux sont caractérisés par la concentration d'une grande partie de son énergie dans une petite fraction de sa durée. C'est-à-dire que peu de leurs coefficients ont des valeurs non nulles, ce qui concentre les informations pertinentes.

	T	Signal Transmis	D	Signal Reçu	T
	Émetteur sous une forme compressée. L'acquisition comprimée a été appliquée à l'estimation des canaux Récepteur Canal ... ...
	donnée FIGURE B.3 -Vecteur de symbole transmis avec T symboles d'apprentissage et D symboles de apprentissage Enfin, l'algorithme d'estimation de canal semi-aveugle (Semiblind Channel Estimation) est une combinaison d'estimation de canal basée sur la séquence d'apprentissage et l'estimation de canal aveugle. Il utilise les symboles d'apprentissage connus et les symboles de données inconnus parcimonieux [8, 15, 18, 20, 25-27]. La structure des canaux parcimonieux peut être exploitée à l'aide d'algorithme d'acquisition comprimée tels que Matching Pursuit (MP) [28], Basis Pursuit FIGURE B.1 -Estimation de Canal données. (BP) [29] et autres [30] conduisant à une meilleure performances d'estimation.
	pour effectuer une estimation de canal.
	Estimation Basée	Estimation de Canal		Estimation de Canal
	sur l'Apprentissage		Aveugle		semi-Aveugle
	FIGURE B.2 -Classification des techniques d'estimation de canal.
	Cette section introduit quelques concepts importants pour la compréhension de cette thèse. Pre-
	Les techniques traditionnelles d'estimation de canal telles que les moindres carrés (least square mièrement, certaines caractéristiques de la radio logicielle sont abordées. Ensuite, le signal par-
	Therefore, efficient hardware implementations of the training phase are required for online -LS) n'exploitent pas la parcimonie des canaux, ce qui entraîne une paramétrisation excessive et cimonieux et la parcimonie sont expliqués. Enfin, les concepts clés sur l'acquisition comprimée
	training situations. des performances médiocres de l'estimateur de canal parcimonieux [2]. En outre, les algorithmes sont présentés et leurs applications illustrées.
	D'autre part, les techniques aveugles (Blind Channel Estimation) se concentrent sur les pro-d'estimation classiques deviennent trop complexes pour traiter ces canaux [20].
	priétés statistiques ou déterministes du système. Elles n'exploitent pas la connaissance de la sé-La caractéristique de parcimonie du signal peut être utilisée pour réduire le coût et la com-Radio Logicielle (SDR) En utilisant des périphériques radio traditionnels basés sur du maté-

L'estimation de canal basée sur l'apprentissage (training based channel estimation) utilise certains symboles connus, la séquence d'apprentissage, envoyés avant et/ou pendant la communication pour estimer le canal des sorties mesurées à la séquence d'apprentissage. La Fig. B.3 illustre le vecteur de symbole transmis avec T symboles connus (séquence d'apprentissage) et D symboles pour representer l'information (les données). Cependant, ces symboles connus consomment de l'énergie et de la bande passante qui ont une incidence sur l'efficacité spectrale du canal en raison de l'utilisation de ressources de communication pour transmettre ces symboles au lieu de transmettre des données. quence d'apprentissage. Le principal avantage des techniques d'estimation de canaux aveugles est la possibilité d'éliminer les séquences d'apprentissage. Néanmoins, en général, ces techniques nécessitent des enregistrements longs, conduisant à un taux de convergence lent [3].

Un canal de communication est généralement modélisé par sa réponse impulsionnelle de canal (CIR), qui est un vecteur dont les éléments représentent les gains complexes associés à chaque composant de trajets multiples du canal. Dans des divers systèmes de communication, tels que la télévision haute définition (HDTV)

[5,[START_REF] Fan | Accurate channel estimation based on bayesian compressive sensing for next-generation wireless broadcasting systems[END_REF]

, le système mmWave

[START_REF] Marzi | Compressive channel estimation and tracking for large arrays in mm-Wave picocells[END_REF][START_REF] Ma | Design and optimization on training sequence for mmWave communications: A new approach for sparse channel estimation in massive MIMO[END_REF]

, large bande HF

[START_REF] Ying | Turbo equalization based on compressive sensing channel estimation in wideband HF systems[END_REF][START_REF] Marques | Compressed sensing for wideband HF channel estimation[END_REF]

,

bande ultralarge

[START_REF] Zhang | A compressed sensing based ultra-wideband communication system[END_REF][START_REF] Cohen | Channel estimation in UWB channels using compressed sensing[END_REF][START_REF] Sharma | A new sparse signal-matched measurement matrix for compressive sensing in UWB communication[END_REF]

, massive MIMO

[START_REF] Rao | Compressive sensing with prior support quality information and application to massive MIMO channel estimation with temporal correlation[END_REF]

et les systèmes de communication sous-marins

[START_REF] Panayirci | Sparse channel estimation and equalization for OFDM-based underwater cooperative systems with amplify-and-forward relaying[END_REF][START_REF] Li | Low computational complexity design over sparse channel estimator in underwater acoustic OFDM communication system[END_REF]

, les canaux peuvent être considérés comme des canaux parcimonieux. En d'autres termes, leurs réponses impulsionnelles sont caractérisées par quelques termes significatifs qui sont largement séparés dans un domaine, c'est-à-dire que de nombreux coefficients sont proches ou égaux à zéro.

En effet, dans les systèmes de communication sans fil, par exemple, plusieurs composants du signal arrivent au récepteur avec un retard dû au multitrajet causé par l'environnement, rendant sa réponse parcimonieuse

[START_REF] Eldar | Compressed Sensing: Theory and Applications[END_REF]

. plexité de son estimation. Par exemple, en utilisant l'acquisition comprimée (compressive sensing -CS), ces signaux peuvent être reconstruits à partir de moins de mesures que celles requises par le théorème d'échantillonnage de Shannon-Nyquist

[START_REF] Berger | Application of compressive sensing to sparse channel estimation[END_REF][START_REF] Candes | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] Donoho | Compressed sensing[END_REF][START_REF] Candes | An introduction to compressive sampling[END_REF][START_REF] Carmi | Compressed Sensing & Sparse Filtering[END_REF]

. LAfin de résoudre certains problèmes liés à ces algorithmes, les réseaux de neurones (NNs) sont de plus en plus utilisés dans les systèmes de communication

[START_REF] Borgerding | AMP-inspired deep networks for sparse linear inverse problems[END_REF][START_REF] He | Deep learning-based channel estimation for beamspace mmWave massive MIMO systems[END_REF][START_REF]A model-driven deep learning network for MIMO detection[END_REF][START_REF] Gregor | Learning fast approximations of sparse coding[END_REF][START_REF] Borgerding | Onsager-corrected deep learning for sparse linear inverse problems[END_REF][START_REF] Wang | Learning deep l 0 encoders[END_REF][START_REF] Metzler | Learned D-AMP: Principled neural network based compressive image recovery[END_REF][START_REF] Sprechmann | Learning efficient sparse and low rank models[END_REF][START_REF] Yao | SURE-TISTA: A signal recovery network for compressed sensing[END_REF][START_REF] Ito | Trainable ISTA for sparse signal recovery[END_REF][START_REF]Trainable ISTA for sparse signal recovery[END_REF][START_REF] Takabe | Complex field-trainable ISTA for linear and nonlinear inverse problems[END_REF]

. Certaines d'entre eux sont basées sur des algorithmes offrant des garanties de performance et les outils de NN, combinant le meilleur des deux.

À partir de l'étude de l'acquisition comprimée, des algorithmes d'acquisition comprimée et de réseau neuronal, cette thèse vise à contribuer au développement d'algorithmes pour l'estimation de canaux parcimonieux. Dans ce travail, l'estimation de canal est formulée comme un problème de récupération de signal. Les approches développées sont destinées à être utilisées dans des applications radio logicielle (SDR). Cependant, elles peuvent être appliquées dans d'autres domaines où le signal d'intérêt peut être considéré comme parcimonieux ou compressible.

B.2 Concepts de Base

riel, une intervention physique est nécessaire pour les modifier, limitant ainsi les fonctionnalités croisées et les coûts de production plus élevés. En revanche, la radio logicielle (SDR) apparaît comme une excellente alternative offrant une solution efficace et relativement peu coûteuse à ce problème

[START_REF] Forum | What is software defined radio?[END_REF]

.

  Cette section traite de plusieurs algorithmes d'acquisition comprimée qui ont été proposés au cours des dernières années. Ces algorithmes doivent récupérer un signal parcimonieux à partir d'un ensemble de mesures sous-échantillonné. Ils sont généralement classés en trois catégories La troisième catégorie est composée des algorithmes "gloutons". Ils récupèrent le signal de manière itérative, en effectuant une sélection optimale locale à chaque itération dans le but de trouver la solution optimale globale à la fin de l'algorithme. L'étude de ces algorithmes a abouti à la proposition d'un algorithme glouton appelé Matching Pursuit based on Least Squares (MPLS) présenté dans la Section 5.1. De plus, les bons résultats de FISTA et la simplicité de ISTA ont stimulé l'étude du réseau neural LISTA et d'autres réseaux neuronaux utilisés pour récupérer de signaux parcimonieux (voir le Chapitre 4).

	B.4 Apprentissage Profond basé sur l'Acquisition Comprimée
	BP LASSO Les algorithmes d'acquisition comprimée qui les ont inspirés sont également illustrés dans cette MP OMP
	figure.	ISTA AMP LARS DS AMP GraDeS	Algorithmes Comprimée d'Acquisition Algorithmes d'acquisition comprimée Gloutons IHT Relaxation Convexe Algorithmes ISTA GOAMP GOMP SP StOMP CoSaMP ROMP
		BCS FOCUSS IRLS	Optimisation Non Convexe	GP MMP IHT
	LAMP	FIGURE B.5 -Classification des algorithmes d'acquisition comprimée. LDAMP DL0RE LISTA SURE-TISTA TISTA
	Les algorithmes de la première catégorie (relaxation convexe) entraînent des problèmes d'op-Réseaux de neurones
	timisation convexe dont les solutions efficaces reposent sur des techniques avancées, telles que les FIGURE B.6 -Les réseaux de neurones inspirés par des algorithmes d'acquisition comprimée
	méthodes de gradient projeté, les méthodes de point intérieur ou le seuillage itératif [18]. présentés dans ce chapitre.
	D'autre part, les approches d'optimisation non convexe peuvent récupérer le signal en tenant
	compte d'une connaissance préalable de sa distribution [57]. Grâce à une fonction de densité

principales : relaxation convexe (convex relaxation), techniques d'optimisation non convexe (nonconvex optimization techniques) et algorithmes gloutons (greedy algorithms) [24]. La Fig. B.5 montre les algorithmes qui sont abordés dans ce chapitre. Après leur descriptions, certaines comparaisons de performances sont analysées.

de probabilité postérieure, ces solutions offrent des statistiques complètes de l'estimation. Néanmoins, ils peuvent ne pas convenir aux problèmes de grandes dimensions en raison de leurs exigences informatiques intensives

[START_REF] Kanevsky | Kalman filtering for compressed sensing[END_REF]

.

Cette section explore certains réseaux de neurones utilisés pour estimer les signaux parcimonieux. Tout d'abord, les concepts clés liés à l'apprentissage en profondeur sont introduits. Ensuite, plusieurs réseaux de neurones proposés dans la littérature sont abordés. Certaines d'entre eux ont été inspirés par les algorithmes d'acquisition comprimée présentés dans le Chapitre 3. La Fig. B.6 montre les réseaux de neurones qui sont abordés plus en détail dans ce chapitre.

BASIC CONCEPTS

Acknowledgements

The last years were full of intense emotions, a mix of cries and laughs, moments of hope and despair, exchanging experiences and knowledge. I thank God for my life, for giving me health and enabling incredible people to cross my path. This thesis would not have been possible without the support of several people who have gone through my life before and during it. They rendered the work and moments of sadness less difficult, making this period of my life unforgettable.

It is very difficult to name all the people who contributed to make this day come. The following

using LISTA (curve LISTA std ), 10% to 15% of the tap attributions are incorrect. On the other hand, with α = 0.02 this percentage of error decreases and this decrease reflects in better NMSE values as can be seen in Fig. 5.11. This occurs because in the "Selection" step, taps with a norm value lower or equal to 0.02E are setting to a zero value removing some improper tap attributions. Moreover, it can be observed from Fig. 5.11 that the α value influences a lot the performance of the estimation. A big value of α (for example α = 0.1) can lead to set a lot of taps to zero resulting in an estimate v with sparsity s lower than h, so generating bigger NMSE values. On the other hand, a small α value (for example α = 0.0) may consider that a lot of taps have non-zero values resulting in an estimate with sparsity s bigger than h.

The influence of α value can be also observed in Table 5.2 [START_REF] Marques | Deep learning approaches for sparse recovery in compressive sensing[END_REF]. This table shows the quantity of layers required to achieve NMSE values equal to -20 dB and -30 dB. It considers the case without using the steps proposed in Fig. 5.10 (Case 1) and the cases using them with different α values (Cases 2 to 5). Table 5.2 -Number of layers required to achieve a given performance using "Tech. 1".

Case Method NMSE

Case 3 shows that with 16 layers and α = 0.02 the NMSE is -30 dB. This value is not achieved even with 20 layers in the case that only the LISTA is used (Case 1). On the other hand, less adjusted values of α may require bigger values of N L (>20) to achieve NMSE close to -30 dB.

Appendix A

List of Publications

B.6 Conclusion et Perspectives

Cette section comprend quelques remarques finales sur le travail actuel et les perspectives.

Cette thèse portait sur l'estimation des canaux parcimonieux et l'exploration de nouvelles approches pour l'estimation des signaux parcimonieux. Une estimation de canal de haute qualité est