wide range of problems in communications and information theory can be cast as sparse recovery tasks, where the objective is to identify the active codewords in a linear superposition with random channel coefficients and additive noise. In multi-antenna systems, it is commonly assumed that the channel coefficients and noise are identically distributed across receive antennas, which implies that the activity pattern is shared among all antennas. By forming outer products of the received signals, such problems can be transformed into structured covariance estimation problems in which the unknown parameters are the variances of the channel coefficients, commonly referred to as large-scale fading coefficients. Characterizing the interplay among the number of receive antennas, pilot symbols, active users, total users, and the resulting error probability is therefore of fundamental importance for the design of efficient random access protocols. In this work, a general class of covariance estimators, defined by a real-valued functiongand a prescribed set of admissible covariance matrices, is studied. Given a possibly perturbed observation of an underlying covariance matrix, the estimator is defined as the minimizer of a sum ofgapplied to the eigenvalues of a suitably normalized matrix, subject to the constraint that the estimate lies in the admissible set. Under mild regularity conditions on the functiongand the constraint set, robustness of this class of estimators is established, in the sense that the estimation error can be made arbitrarily small as the perturbation vanishes. These general results are applied to activity detection in random access systems with multiple receive antennas. Recovery via nonnegative least squares and via a relaxed maximum-likelihood estimator is considered, and it is shown that, under suitable assumptions on the channel and noise distributions, the relaxed maximum-likelihood estimator belongs to the proposed class of covariance estimators. Finally, pilot codebooks satisfying a signed kernel condition are introduced and it is shown that, with such codebooks, reliable recovery of the large-scale fading coefficients is possible when the number of receive antennas is sufficiently large and the number of active users satisfiesS≤ [1/2M2] − 1, whereMdenotes the number of pilot symbols per user. For the finite-antenna regime, refined recovery conditions that explicitly capture the dependence on the number of receive antennas are derived.