Umeå University's logo

The hierarchical sparsity framework, and in particular the HiHTP algorithm(Hierarchical Hard Thresholding Pursuit), has been successfully applied to many relevant communication engineering problems recently, particularly when the signal space is hierarchically structured. In this paper, the applicability of the HiHTP algorithm for solving the bi-sparse blind deconvolution problem is studied. The bi-sparse blind deconvolution setting here consists of recovering h and b from the knowledge of h*Qb, where Q is some linear operator, and both b and h are assumed to be sparse. The approach rests upon lifting the problem to a linear one, and then applying HiHTP, through the hierarchical sparsity framework. Then, for a Gaussian draw of the random matrix Q, it is theoretically shown that an s-sparse h in R^mu and sigma-sparse b in Rⁿ with high probability can be recovered when s > C s*log(s)²*sigma*log(mu)*log(mu*n) + s*sigma*log(n) .

We propose an adaptive refinement algorithm to solve total variation regularized measure optimization problems. The method iteratively constructs dyadic partitions of the unit cube based on (i) the resolution of discretized dual problems and (ii) the detection of cells containing points that violate the dual constraints. The detection is based on upper-bounds on the dual certificate, in the spirit of branch-and-bound methods. The interest of this approach is that it avoids the use of heuristic approaches to find the maximizers of dual certificates. We prove the convergence of this approach under mild hypotheses and a linear convergence rate under additional non-degeneracy assumptions. These results are confirmed by simple numerical experiments.1

We investigate the optimization of neural networks on symmetric data, and compare the strategy of constraining the architecture to be equivariant to that of using data augmentation. Our analysis reveals that the relative geometry of the admissible and the equivariant layers, respectively, plays a key role. Under natural assumptions on the data, network, loss, and group of symmetries, we show that compatibility of the spaces of admissible layers and equivariant layers, in the sense that the corresponding orthogonal projections commute, implies that the sets of equivariant stationary points are identical for the two strategies. If the linear layers of the network also are given a unitary parametrization, the set of equivariant layers is even invariant under the gradient flow for augmented models. Our analysis however also reveals that even in the latter situation, stationary points may be unstable for augmented training although they are stable for the manifestly equivariant models.

Secret key generation (SKG) between authenticateddevices is a pivotal task for secure communications. Diffie-Hellman (DH) is de-facto standard but not post-quantum secure.In this paper, we shall invent and analyze a new security primitivethat is specifically designed for WPAN. For WPAN, wirelesschannel-based SKG has been proposed but was not widelydeployed due to its critical dependence on the channel’s entropywhich is uncontrollable. We formulate a different approach:We still exploit channel properties but mainly hinge on thereciprocity of the wireless channel and not on the channel’sentropy. The radio advantage comes from the use of full duplexcommunication. We show that in this situation both legitimateparties can agree on a common secret key even without everprobing the channel at all. At the core is a new bisparseblind deconvolution scheme for which we prove correctnessand information-theoretic, i.e. perfect, security. We show that,ultimately, a secret key can be extracted and give a lower boundfor the number of secret key bits which is then verified byexperiments

Equivariance of linear neural network layers is well studied. In this work, we relax the equivariance condition to only be true in a projective sense. Hereby, we introduce the topic of projective equivariance to the machine learning audience. We theoretically study the relation of projectively and linearly equivariant linear layers. We find that in some important cases, surprisingly, the two types of layers coincide. We also propose a way to construct a projectively equivariant neural network, which boils down to building a standard equivariant network where the linear group representations acting on each intermediate feature space are lifts of projective group representations. Projective equivari-ance is showcased in two simple experiments. Code for the experiments is provided at github.com/usinedepain/projectively_equivariant_deep_nets

Secret key generation between authenticated devices is a pivotal task for secure communications. Diffie-Hellman (DH) is de-facto standard but not post-quantum secure. In this paper, we shall invent and analyze a new security primitive that is specifically designed for WPAN. For WPAN, wireless channel-based secret key generation has been proposed but was not widely deployed due to its critical dependence on the channel’s entropy which is uncontrollable. We formulate a different approach: We still exploit channel properties but mainly hinge on the reciprocity of the wireless channel and not on the channel’s entropy. The radio advantage comes from the use of full duplex communication. We show that in this situation both legitimate parties can agree on a common secret key even without ever probing the channel. At the core is a new bisparse blind deconvolution scheme for which we prove correctness and information-theoretic, i.e. perfect, security. We show that, ultimately, a secret key can be extracted and give a lower bound for the number of secret key bits which is then verified by experiments. We also notice a remote correspondence of the scheme to DH key exchange.

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.

We characterize the class of image plane transformations which realize rigid camera motions and call these transformations ‘rigidity preserving’. It turns out that the only rigidity preserving image transformations are homographies corresponding to rotating the camera. In particular, 2D translations of pinhole images are not rigidity preserving. Hence, when using CNNs for 3D inference tasks, it can be beneficial to modify the inductive bias from equivariance w.r.t. translations to equivariance w.r.t. rotational homographies. We investigate how equivariance with respect to rotational homographies can be approximated in CNNs, and test our ideas on 6D object pose estimation. Experimentally, we improve on a competitive baseline.

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.