PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-Bayesian Activity Detection, Large-Scale Fading Coefficient Estimation, and Unsourced Random Access with a Massive MIMO Receiver

Alexander Fengler, Saeid Haghighatshoar, Peter Jung, Giuseppe Caire

arXiv:1910.11266v3cs.IT

TL;DR

The paper addresses the signal-dimension limitation in reliable activity identification and develops an approach based on Non-Negative Least-Squares analysis. It shows that massive antenna arrays support activity estimation beyond the traditional compressed-sensing bound, with reliable communication and growing spectral efficiency.

  • Problem

    Reliable activity identification is constrained by the signal dimension L, motivating methods that avoid devoting too many pilot dimensions to activity detection.

  • Method

    The paper analyzes Non-Negative Least-Squares for estimating large-scale fading coefficients and identifying active users.

  • Results

    Ka = O(L2/ log2(Ktot/Ka)) active users can be reliably estimated among Ktot users, exceeding the traditional Ka = O(L) compressed-sensing bound.

  • Takeaways & Limitations

    An arbitrarily fixed error probability is achievable at any Eb/N0 with sufficiently many antennas, while total spectral efficiency grows as O(L log L).

  • Takeaways & Limitations

    The discussion assumes gk = 1 for all k.

Abstract

from arXiv · show

In this paper, we study the problem of user activity detection and large-scale fading coefficient estimation in a random access wireless uplink with a massive MIMO base station with a large number $M$ of antennas and a large number of wireless single-antenna devices (users). We consider a block fading channel model where the $M$-dimensional channel vector of each user remains constant over a coherence block containing $L$ signal dimensions in time-frequency. In the considered setting, the number of potential users $K_\text{tot}$ is much larger than $L$ but at each time slot only $K_a<<K_\text{tot}$ of them are active. Previous results, based on compressed sensing, require that $K_a\leq L$, which is a bottleneck in massive deployment scenarios such as Internet-of-Things and unsourced random access. In this work we show that such limitation can be overcome when the number of base station antennas $M$ is sufficiently large. We also provide two algorithms. One is based on Non-Negative Least-Squares, for which the above scaling result can be rigorously proved. The other consists of a low-complexity iterative componentwise minimization of the likelihood function of the underlying problem. Finally, we use the discussed approximated ML algorithm as the decoder for the inner code in a concatenated coding scheme for unsourced random access, a grant-free uncoordinated multiple access scheme where all users make use of the same codebook, and the massive MIMO base station must come up with the list of transmitted messages irrespectively of the identity of the transmitters. We show that reliable communication is possible at any $E_b/N_0$ provided that a sufficiently large number of base station antennas is used, and that a sum spectral efficiency in the order of $\mathcal{O}(L\log(L))$ is achievable.

I. INTRODUCTION

The paper develops non-Bayesian activity detection and large-scale fading estimation for massive-MIMO random access, addressing the conventional Ka = O(L) bottleneck. It also applies the detector to unsourced random access, where users share a codebook and the receiver decodes messages without transmitter identities.

  • I. INTRODUCTION: The proposed non-Bayesian approach treats large-scale fading coefficients as deterministic unknowns rather than requiring known values or prior distributions.NNLS is applied to sample covariance information to estimate fading coefficients and activity.
  • I. INTRODUCTION: NNLS recovery guarantees are rigorously established, while the low-complexity iterative ML algorithm is supported by numerical evidence and has lower complexity than EM.The constrained ML scaling law matches NNLS up to logarithmic factors in M, whereas the constrained ML optimization itself is combinatorial.
  • I. INTRODUCTION: The massive-MIMO detector serves as the inner decoder in a concatenated unsourced-random-access scheme that avoids dependence on inactive-user count and large pilot dimensions.All users use the same codebook, and the receiver recovers transmitted messages irrespective of transmitter identity.
  • I. INTRODUCTION: Arbitrarily small error probability is achievable at any Eb/N0 with sufficiently many antennas, while sum spectral efficiency grows as O(L log(L)).The scheme operates non-coherently, without requiring channel-matrix estimation.

A. Notation

The paper establishes notation and models pilot-based activity detection over a block-fading massive-MIMO uplink. It defines the active LSFC pattern, observation model, channel assumptions, and estimation goals.

  • Signal model: Each potential user has a known length-L pilot, and active users transmit its components during the activity-detection slot.
  • Signal model: The received signal combines pilot transmissions weighted by activity and large-scale fading coefficients with additive white Gaussian noise.
  • Signal model: The compact model uses the pilot matrix A, diagonal activity-weighted LSFC matrix Γ, normalized channel matrix H, and noise Z.
  • Channel assumptions: Under independent spatially white Rayleigh fading, user channel vectors are independent and distributed as CN(0, I_M).
  • Estimation goals: Activity detection identifies active users or sufficiently strong users, while LSFC estimation targets their channel strengths for network operations.

III. PROPOSED ALGORITHMS FOR ACTIVITY DETECTION

This section develops ML-based activity detection and LSFC estimation, then motivates relaxed and iterative alternatives. Theorem 1 shows that sufficiently many antennas allow detection beyond the conventional Ka≤L regime.

  • The paper presents two algorithms for activity detection and large-scale fading coefficient estimation.
  • Maximum Likelihood estimation: The constrained ML estimator assumes a known active-user count and searches binary Ka-sparse activity patterns using the Gaussian likelihood.
  • Maximum Likelihood estimation: The constrained ML formulation is impractical because Ka is usually unknown and its combinatorial minimization has exponential complexity in Ktot.
  • Relaxed and iterative ML: The relaxed likelihood estimator avoids prior knowledge of Ka but is generally nonconvex; its componentwise solver has strong empirical convergence despite lacking a global guarantee.
  • Maximum Likelihood estimation: Theorem 1 guarantees correct activity recovery with high probability under random pilots, bounded LSFCs, and sufficient system scaling.
  • Maximum Likelihood estimation: Ka can exceed L, but the antenna count must grow at least as fast as (Ka/L)^2.

B. Non-Negative Least Squares

The NNLS approach converts covariance-based estimation into a nonnegative least-squares problem with rigorous recovery guarantees. Its scaling permits activity levels on the order of L^2 with only polylogarithmic dependence on Ktot.

  • Formulation: The paper formulates LSFC estimation as a linear least-squares problem with a non-negativity constraint, namely NNLS.
  • RIP analysis: Theorem 2 establishes high-probability RIP for the centered pilot matrix under a sparsity scaling involving L^2 and logarithmic factors in Ktot.
  • Recovery guarantee: As M→∞, the estimation error vanishes under the same scaling condition used for the activity-detection result.
  • RIP analysis: A centered and rescaled pilot matrix is analyzed through the restricted isometry property to control sparse recovery.
  • Recovery guarantee: For s=Ka, the NNLS guarantee yields exact recovery up to the stated noise term because the tail after the largest s components vanishes.
  • Scaling law: The NNLS estimator can identify up to O(L^2) active users with a polylogarithmic penalty as Ktot increases.

C. Iterative Algorithms

The iterative algorithms update one LSFC coordinate at a time by minimizing the relevant objective. Rank-1 updates enable efficient implementation, with convergence guarantees for NNLS but not generally for ML.

  • The unified scheme performs componentwise minimization over the nonnegative orthant, updating one coordinate γk at each iteration.
  • ML iteration: ML updates use the derived one-dimensional likelihood minimization, with variants differing in initialization and coordinate-selection rules.
  • The noise variance σ^2 may be jointly estimated with γ as an additional optimization parameter.
  • NNLS iteration: The same iterative approach applies to NNLS with a different coordinate update, and convexity guarantees convergence to the NNLS solution.

1) ML and NNLS with Knowledge of the LSFCs

The paper presents non-Bayesian ML and NNLS activity-detection methods that use sample covariance data, optionally incorporating known LSFCs through constraints and thresholds. Bayesian MMV-AMP is reviewed as a contrasting approach based on assumed LSFC knowledge or distributions.

  • Known LSFCs: Known LSFCs enable coordinate updates constrained to [0, g_k] and thresholds calibrated to channel strength.The box constraint is applied when the true LSFC vector is available at the receiver.
  • Algorithms: ML and NNLS operate on the sample covariance matrix and can use known LSFCs as algorithm inputs.Algorithm 1 initializes with the sample covariance and optionally receives all users’ LSFCs.
  • Evaluation: The relative ℓ1 error is used to evaluate LSFC estimation because the coefficients represent received signal powers.An ℓ2 square-error metric is considered less physically meaningful for these coefficients.
  • Algorithmic assumptions: The ML objective is non-convex, whereas MMV-AMP uses posterior-mean denoisers under Bayesian LSFC assumptions.MMV-AMP assumes independent user rows and either known LSFCs or a known LSFC distribution.
  • MMV-AMP: State evolution recursively supplies the effective noise covariance and asymptotically predicts AMP estimation error.The covariance begins at Σ_0 = σ^2I_M + K_tot and remains diagonal under uncorrelated antennas.

1) MMV-AMP Scaling

MMV-AMP state-evolution analysis predicts vanishing activity-detection error as M grows, but its limit order does not capture the paper’s joint scaling regime. Simulations reveal non-convergence and substantial deviations from state-evolution predictions in practically relevant regimes.

  • Asymptotic prediction: As M →∞, state-evolution analysis predicts vanishing activity-detection error for any number of active users.This analysis first takes Ka, L →∞ at fixed M and then lets M →∞.
  • Scaling limitations: The successive limits assume Ka is much larger than M and cannot derive a scaling relation between M and Ka.They therefore do not generally capture regimes where Ka is essentially quadratic in L and M grows slightly faster than Ka.
  • Approximations: Approximating the AMP derivative reduces complexity from O(M^2) to O(M) and can reduce samples that fail to match state-evolution predictions.This approximation barely changes performance in a large-parameter regime.
  • LSFC effects: Large LSFC dynamic ranges increase the frequency of unstable AMP behavior, whereas constant or small-range LSFCs reduce or eliminate it.The behavior is reported across random pilot, channel, and noise realizations.
  • Practical behavior: MMV-AMP can exhibit random non-convergent behavior when M > Ka > L, where discarding antennas is not possible because M > Ka measurements are needed.The observed performance can differ significantly from state-evolution predictions in this regime.

C. Complexity Comparison

Covariance-based ML and NNLS scale better with the antenna count, while MMV-AMP scales better with coherence-block length. Simulations show that ML and NNLS retain favorable activity and LSFC-recovery behavior beyond the compressed-sensing regime, where MMV-AMP deteriorates.

  • Complexity: Covariance-based ML and NNLS have complexity O(K_tot L^2) plus an empirical-covariance calculation linear in ML.MMV-AMP instead costs O(M^2 L K_tot), or O(M^2 K_tot log K_tot) with a sub-sampled FFT pilot matrix.
  • Complexity: The simplified MMV-AMP derivative reduces complexity to min(O(MK_tot log K_tot), O(MK_totL)).Overall, covariance-based algorithms scale better with M, whereas MMV-AMP scales better with L.
  • Activity detection: Beyond the CS regime, MMV-AMP performance significantly deteriorates, while ML and NNLS activity-detection error probabilities continue to decay with M.At the CS boundary, NNLS is comparably worse than MMV-AMP and ML when M is small relative to L.
  • Scaling: M = O((K_a/L)^2) antennas, up to constant or logarithmic factors, describes the ML scaling in the K_a ≤ L regime.The error probability decays faster there than when K_a > L, matching Theorem 1 qualitatively.
  • LSFC estimation: As M →∞, NNLS recovery error vanishes under condition (15), and simulations show a similar phase-transition behavior for ML.The NNLS phase transition follows a quadratic curve, while ML exhibits very similar behavior.

A. Unsourced random access as AD problem

The paper maps unsourced random access inner decoding to the same covariance-based activity-detection problem by treating transmitted codewords as candidate messages. Its non-Bayesian ML decoder identifies active messages without channel estimation and supports favorable massive-MIMO scaling.

  • Code construction: Each column of the coding matrix represents one J-bit inner codeword, and active users transmit the corresponding columns.The same codebook is shared across users, as required by unsourced random access.
  • AD formulation: For 2^J significantly larger than K_a, the transformed signal matrix is row-sparse because each row is zero with probability (1 − 2^-J)^K_a.Nonzero rows correspond to transmitted messages, including collisions whose powers add positively.
  • AD formulation: The inner decoder estimates the modified LSFC pattern γ, whose nonzero indices identify transmitted messages.The resulting formulation is analogous to activity detection, with 2^J messages replacing K_tot potential users.
  • Non-coherent decoding: Non-coherent power-domain detection avoids signal cancellation or destructive interference when multiple users select the same sub-message.The decoder does not explicitly estimate the complex channel matrix.
  • Decoder choice: The ML algorithm is used as the inner decoder because modified LSFCs have unknown random-sum values and statistics, making Bayesian modeling inconvenient.Averaging over active subsets to obtain those statistics would have exponential complexity in K_tot.
  • Scaling results: K_a = O(L^2) and sum spectral efficiency O(L log L) are achievable under the stated message and antenna scaling conditions.The error probability can be made as small as desired for any given E_b/N_0 > 0, although per-user rate vanishes as log(L)/L.

D. Asymptotic analysis - Outer code

The outer-code analysis characterizes achievable rates and decoding complexity in the logarithmic regime, while identifying a converse and an unresolved coding question in another scaling regime.

  • In the typical regime K_a ≪ 2^J, the componentwise entropy upper bound is tight because it is achievable by the outer code of.
  • The evenly distributed parity-bit construction has decoding complexity O(SK_a log K_a), scaling linearly with the number of subslots S.
  • R_out = 1 − 1/α with all parity bits in the last sections, while R_out = 1 − c/α with evenly distributed parity bits.
  • The inner-code error probability vanishes when K_a = O(L^2/log^2(L)) in the logarithmic regime, yielding a sum spectral efficiency whose order is smaller by a factor log_2 L than in the OR-MAC analysis.
  • 2) Converse: When 2^J = δK_a with δ > 1, the best achievable asymptotic per-user outer rate tends to zero, although the outer sum rate remains proportional to K_a.
  • 2) Converse: An outer code achieving the entropy bound in this regime could increase sum spectral efficiency by a factor log L, but whether the code of or another code can do so remains unclear.

E. Simulations

The simulations evaluate activity detection and unsourced random access under varied user loads, antenna counts, energy, and coherence-block configurations. They support the predicted scaling with receiver antennas and coherence length, while identifying practical codebook-size and algorithmic limitations.

  • Activity detection: Threshold selection balances missed detections against false alarms when forming hard activity decisions.Fixed thresholds mark components of each estimated activity vector above ν_s.
  • Simulation results: With K_a = 300, the simulations obtain total spectral efficiency μ ≈9 bits per channel use.The reported per-user efficiency is R ≈0.031 bits per channel use under the stated n and payload configuration.
  • Simulation results: 20 dB or more energy gains are possible with multiple receive antennas relative to the scalar Gaussian multiple-access benchmark.The benchmark requires approximately 17.5 dB for total spectral efficiency 9 bits per channel use, whereas the massive-MIMO setting achieves gains of 20 dB or more.
  • Algorithm comparison: MMV-AMP exhibits unstable behavior when the number of receiver antennas is large, the regime targeted by massive MIMO.This instability appeared as a byproduct of the numerical investigation.
  • Unsourced random access: Increasing receiver antennas can make the error probability arbitrarily small at any E_b/N_0 and support sum spectral efficiency O(L log L).The conclusion states these results for sufficiently many antennas and code block length L.
  • Practical limitations: The one-shot scheme is impractical for payloads around B ≈100 bits because its codebook requires 2^B columns.The paper therefore considers a concatenated approach with smaller blocks and an outer code.
  • Unsourced random access: The concatenated scheme uses smaller message blocks, activity detection as an inner decoder, and an outer tree code to stitch decoded submessages.Simulations report the proposed method's effectiveness for this architecture.
  • Receiver operation: The receiver avoids pilot overhead because it never estimates the massive-MIMO complex fading channel matrix.The proposed schemes are completely non-coherent and do not incur the pilot-symbol overhead associated with ideal coherent reception.

APPENDIX A

This appendix establishes recovery guarantees by analyzing likelihood separation through Rényi divergence and strong convexity, supported by a new RIP result.

  • RIP foundation: A new RIP result repairs an earlier claimed-and-retracted property for the non-centered matrix model.The revised result is used to establish the needed restricted-isometry behavior.
  • Recovery proof: The union-bound argument combines likelihood concentration, divergence lower bounds, and sparse-support counting to complete the recovery proof.The proof concludes when the stated antenna and pilot-matrix conditions hold.
  • Likelihood separation: The proof lower-bounds Rényi divergence between candidate and true Gaussian models using strong convexity of ψ(b) = −log |Σ(b)|.Theorem 4 requires positive Rényi divergence, which is obtained by proving strong convexity on sparse vectors.
  • Likelihood separation: With RIP of order 2K_a and an appropriate constant, ψ is strongly convex between any two K_a-sparse vectors.The resulting bound is uniform over the sparse-vector set with high probability.

APPENDIX B

This appendix proves the RIP property needed by the recovery analysis for pilot matrices, using concentration results for independent sub-exponential columns and spherical pilots.

  • Generic RIP result: The generic RIP theorem gives δ_2s(R/√m) < δ with high probability for matrices with independent normalized columns under tail and dimension conditions.The probability and constants depend on the stated sub-exponential and concentration assumptions.
  • Application to pilots: The proof applies the generic theorem to a real matrix formed by stacking the real and imaginary parts of the centered pilot matrix.The construction uses m = 2L(L−1) and N = K_tot.
  • Pilot concentration: Uniform spherical pilot vectors satisfy dimension-independent concentration properties that yield sub-exponential columns for the real-valued matrix.The argument uses convex concentration, the Hanson-Wright inequality, and concentration on the sphere.
  • RIP conclusion: The resulting real and complex centered matrices satisfy the required RIP with high probability.The proof transfers the RIP from the real representation back to the complex matrix.
  • Scope boundary: If the number of users grows exponentially with the signal dimension, the theorem’s constraint can force the achievable sparsity level s to vanish.This is the stated boundary of the RIP scaling argument.

APPENDIX C

This appendix derives the NNLS recovery guarantee from robust nullspace properties, then obtains those properties from RIP of the centered pilot matrix.

  • Problem representation: The measurement matrix A is built from vectorized pilot outer products, while the observation perturbation is represented by d = vec(Σ_y − bΣ_y).The proof applies the NNLS theorem with the true activity pattern and empirical covariance observations.
  • NNLS guarantee: The NNLS guarantee assumes robust ℓ2-NSP of order s together with a vector t satisfying 1 = A^H t.Under these conditions, the NNLS estimate obeys the theorem’s error bound for p ∈ [1, 2].
  • From RIP to NSP: The centered matrix’s RIP implies robust ℓ2-NSP, and the special matrix structure transfers the property to the uncentered matrix A.The transfer preserves the order and the relevant constants.
  • Explicit constants: For example, choosing δ = 0.5 gives ρ < 0.68 and τ < 3/L for the centered matrix.These explicit constants feed into the NNLS recovery bound.
  • Proof conclusion: Combining the RIP-to-NSP result with the NNLS theorem completes the proof of the recovery guarantee.The conclusion follows by applying the theorem to the true activity vector and empirical covariance measurements.

APPENDIX D

This appendix bounds sample-covariance deviations using concentration of Gaussian observations and extends the result to non-diagonal covariance matrices and broader component distributions.

  • Diagonal covariance: For diagonal covariance matrices, the appendix analyzes normalized covariance entries and bounds their sample deviations using sub-exponential concentration.The entrywise variance calculation gives E[|Δ_ij|^2] = β_iβ_j.
  • Concentration bound: The resulting deviation bound holds with probability exceeding 1 − ϵ when cM > log(2(eL)^2/ϵ).The sample size M therefore controls concentration of the empirical covariance around its mean.
  • General covariance: For non-diagonal covariance matrices, unitary diagonalization and Frobenius-norm invariance extend the bound beyond the diagonal case.The generalized result depends on the covariance matrix through its trace.
  • Distributional extension: Although the derivation assumes Gaussian observations, the result can be modified for general component distributions.The modified bound introduces a multiplicative factor max{ς −1, 1}.
Loading 1910.11266v3…