A Survey: Non-Orthogonal Multiple Access with Compressed Sensing Multiuser Detection for mMTC <s> Compressive sensing basics <s> The time-frequency and time-scale communities have recently developed a large number of overcomplete waveform dictionaries --- stationary wavelets, wavelet packets, cosine packets, chirplets, and warplets, to name a few. Decomposition into overcomplete systems is not unique, and several methods for decomposition have been proposed, including the method of frames (MOF), Matching pursuit (MP), and, for special dictionaries, the best orthogonal basis (BOB). ::: Basis Pursuit (BP) is a principle for decomposing a signal into an "optimal" superposition of dictionary elements, where optimal means having the smallest l1 norm of coefficients among all such decompositions. We give examples exhibiting several advantages over MOF, MP, and BOB, including better sparsity and superresolution. BP has interesting relations to ideas in areas as diverse as ill-posed problems, in abstract harmonic analysis, total variation denoising, and multiscale edge denoising. ::: BP in highly overcomplete dictionaries leads to large-scale optimization problems. With signals of length 8192 and a wavelet packet dictionary, one gets an equivalent linear program of size 8192 by 212,992. Such problems can be attacked successfully only because of recent advances in linear programming by interior-point methods. We obtain reasonable success with a primal-dual logarithmic barrier method and conjugate-gradient solver. <s> BIB001 </s> A Survey: Non-Orthogonal Multiple Access with Compressed Sensing Multiuser Detection for mMTC <s> Compressive sensing basics <s> Conventional approaches to sampling signals or images follow Shannon's theorem: the sampling rate must be at least twice the maximum frequency present in the signal (Nyquist rate). In the field of data conversion, standard analog-to-digital converter (ADC) technology implements the usual quantized Shannon representation - the signal is uniformly sampled at or above the Nyquist rate. This article surveys the theory of compressive sampling, also known as compressed sensing or CS, a novel sensing/sampling paradigm that goes against the common wisdom in data acquisition. CS theory asserts that one can recover certain signals and images from far fewer samples or measurements than traditional methods use. <s> BIB002
Compressed sensing (CS) is a signal processing technique which samples a sparse signal at a rate much less than the Nyquist rate BIB002 . A signal x ∈ C K×1 is said to be K a -sparse if it has only K a non-zero elements, K a K. The signal x can be sparse with respect to any basis Φ. Let z = Φx be a compressible signal with respect to Φ. The CS encoding process produces measurement y ∈ C N ×1 by a measurement matrix Ψ ∈ C N ×K , K a < N < K, where n is the background noise vector. The measurement matrix Ψ and the basis Φ should have low coherence The reconstruction of vector x is finding a sparse vectorx which satisfies Equation (1). As Equation (1) is an underdetermined system of equations, the reconstruction of vector x is formulated asx = arg min Where . 0 is the l 0 norm which simply gives the total number of non-zeros elements in the vector. Equation (2) is a non-convex optimization problem, which is known to be NP-hard to solve. Certain relaxation approaches are used to solve Equation (2) such as, basis pursuit denoising BIB001 in which the l 0 norm is relaxed to l 1 norm. The l 1 minimization is a convex optimization problem which recovers the signal from an undermined system of equations with higher accuracy at the cost of higher complexity of cubic order. Another category of compressive sensing reconstruction algorithms is greedy algorithms. In greedy algorithms, e.g., orthogonal matching pursuit (OMP), the support ofx is obtained iteratively by selecting the column of Ψ which has maximum correlation with the residual. The residual is initialized to y and is updated in each iteration of OMP. Once the support is obtained, the corresponding data is estimated by using least square estimation. The greedy algorithms have lower complexity compared to the basis pursuit algorithms at the cost of slightly poor performance.