Beyond its widespread application in signal and image processing, \emph{compressed sensing} principles have been greatly applied to secure information transmission (often termed 'compressive security'). In this scenario, the measurement matrix $Q$ acts as a one time pad encryption key (in complex number domain) which can achieve perfect information-theoretic security together with other benefits such as reduced complexity and energy efficiency particularly useful in IoT. However, unless the matrix is changed for every message it is vulnerable towards known plain text attacks: only $n$ observations suffices to recover a key $Q$ with $n$ columns. In this paper, we invent and analyze a new method (termed 'Bilinear Compressive Security (BCS)') addressing these shortcomings: In addition to the linear encoding of the message $x$ with a matrix $Q$, the sender convolves the resulting vector with a randomly generated filter $h$. Assuming that $h$ and $x$ are sparse, the receiver can then recover $x$ without knowledge of $h$ from $y=h*Qx$ through blind deconvolution. We study a rather idealized known plaintext attack for recovering $Q$ from repeated observations of $y$'s for different, known $x_k$, with varying and unknown $h$ ,giving Eve a number of advantages not present in practice. Our main result for BCS states that under a weak symmetry condition on the filter $h$, recovering $Q$ will require extensive sampling from transmissions of $Ω\left(\max\left(n,(n/s)^2\right)\right)$ messages $x_k$ if they are $s$-sparse. Remarkably, with $s=1$ it is impossible to recover the key. In this way, the scheme is much safer than standard compressed sensing even though our assumptions are much in favor towards a potential attacker.

Compressive Sensing (CS) has well boosted massive random access protocols over the last decade. Usually, on physical layer, the protocols employ some fat matrix with the property that sparse vectors in the much larger column space domain can still be recovered. This, in turn, greatly reduces the chances of collisions between access devices. This basic scheme has meanwhile been enhanced in various directions but the system cannot operate in overload regime, i.e. sustain significantly more users than the row dimension of the fat matrix dictates. In this paper, we take a different route and apply an orthogonal DFT basis as it is used in OFDM, but subdivide its image into so-called sub-channels and let each sub-channel take only a fraction of the load. In a random fashion the subdivision is consecutively applied over a suitable number of time-slots. Within the time-slots the users will not change their sub-channel assignment and send in parallel the data. Activity detection is carried out jointly across time-slots in each of the sub-channels. For such system design we derive three rather fundamental results: i) First, we prove that the subdivision can be driven to the extent that the activity in each sub-channel is sparse by design. An effect that we call sparsity capture effect. ii) Second, we prove that effectively the system can sustain any overload situation relative to the DFT dimension, i.e. detection failure of active and non-active users can be kept below any desired threshold regardless of the number of users. The only price to pay is delay, i.e. the number of time-slots over which cross-detection is performed. We achieve this by jointly exploring the effect of measure concentration in time and frequency and careful system parameter scaling. iii) Third, we prove that parallel to activity detection active users can carry one symbol per pilot and time-slot so it supports so-called one-shot messaging. The key to proving these results are new concentration results for sequences of randomly sub-sampled DFTs detecting the sparse vectors “en bloc”. Eventually, we show by simulations that the system is scalable resulting in a coarsely 20-fold capacity increase compared to standard OFDM.

In this paper, we are concerned with rotation equivariance on 2D point cloud data. We describe a particular set of functions able to approximate any continuous rotation equivariant and permutation invariant function. Based on this result, we propose a novel neural network architecture for processing 2D point clouds and we prove its universality for approximating functions exhibiting these symmetries. We also show how to extend the architecture to accept a set of 2D-2D correspondences as indata, while maintaining similar equivariance properties. Experiments are presented on the estimation of essential matrices in stereo vision.

This paper treats the recovery of sparse, binary signals through box-constrained basis pursuit using biased measurement matrices. Using a probabilistic model, we provide conditions under which the recovery of both sparse and saturated binary signals is very likely. In fact, we also show that under the same condition, the solution of the boxed-constrained basis pursuit program can be found using boxed-constrained least squares.

Numerical evidence suggests that compressive sensing (CS) approaches for wideband massive MIMO channel estimation can achieve very good performance with limited training overhead by exploiting the sparsity of the physical channel. However, analytical characterization of the (minimum) training overhead requirements is still an open issue. By observing that the wideband massive MIMO channel can be represented by a vector that is not simply sparse but has well defined structural properties, referred to as hierarchical sparsity, we propose low complexity channel estimators for the uplink multiuser scenario that take this property into account. By employing the framework of the hierarchical restricted isometry property, rigorous performance guarantees for these algorithms are provided suggesting concrete design goals for the user pilot sequences. For a specific design, we analytically characterize the scaling of the required pilot overhead with increasing number of antennas and bandwidth, revealing that, as long as the number of antennas is sufficiently large, it is independent of the per user channel sparsity level as well as the number of active users. These analytical insights are verified by simulations demonstrating also the superiority of the proposed algorithm over conventional CS algorithms that ignore the hierarchical sparsity property.

Compressed sensing deals with the recovery of sparse signals from linear measurements. Without any additional information, it is possible to recover an s-sparse signal using m > s log(d/s) measurements in a robust and stable way. Some applications provide additional information, such as on the location the support of the signal. Using this information, it is conceivable that the threshold amount of measurements can be lowered. A proposed algorithm for this task is weighted l1-minimization. Put shortly, one modifies standard 11-minimization by assigning different weights to different parts of the index set [1, ... d]. The task of choosing the weights is, however, non-trivial. This paper provides a complete answer to the question of an optimal choice of the weights. In fact, it is shown that it is possible to directly calculate unique weights that are optimal in the sense that the threshold amount of measurements needed for exact recovery is minimized. The proof uses recent results about the connection between convex geometry and compressed sensing-type algorithms.