Learning algorithms that divide the data into batches are prevalent in many machine-learning applications, typically offering useful trade-offs between computational efficiency and performance. In this paper, we examine the benefits of batch-partitioning through the lens of a minimum-norm overparametrized linear regression model with isotropic Gaussian features. We suggest a natural small-batch version of the minimum-norm estimator and derive bounds on its quadratic risk. We then characterize the optimal batch size and show it is inversely proportional to the noise level, as well as to the overparametrization ratio. In contrast to minimum-norm, our estimator admits a stable risk behavior that is monotonically increasing in the overparametrization ratio, eliminating both the blowup at the interpolation point and the double-descent phenomenon. We further show that shrinking the batch minimum-norm estimator by a factor equal to the Weiner coefficient further stabilizes it and results in lower quadratic risk in all settings. Interestingly, we observe that the implicit regularization offered by the batch partition is partially explained by feature overlap between the batches. Our bound is derived via a novel combination of techniques, in particular normal approximation in the Wasserstein metric of noisy projections over random subspaces.

Let$G$be a large (simple, unlabeled) dense graph on$n$vertices. Suppose that we only know, or can estimate, the empirical distribution of the number of subgraphs$F$that each vertex in$G$participates in, for some fixed small graph$F$. How many other graphs would look essentially the same to us, i.e., would have a similar local structure? In this paper, we derive upper and lower bounds on the number of graphs whose empirical distribution lies close (in the Kolmogorov-Smirnov distance) to that of$G$. Our bounds are given as solutions to a maximum entropy problem on random graphs of a fixed size$k$that does not depend on$n$, under$d$global density constraints. The bounds are asymptotically close, with a gap that vanishes with$d$at a rate that depends on the concentration function of the distribution at the center of the Kolmogorov-Smirnov ball.

Let G be a large (simple, unlabeled) dense graph on n vertices. Suppose that we only know, or can estimate, the empirical distribution of the number of subgraphs F that each vertex in G participates in, for some fixed small graph F. How many other graphs would look essentially the same to us, i.e., would have a similar local structure? In this paper, we derive upper and lower bounds on the number graphs whose empirical distribution lies close (in the Kolmogorov-Smirnov distance) to that of G. Our bounds are given as solutions to a maximum entropy problem on random graphs of a fixed size k that does not depend on n, under d global density constraints. The bounds are asymptotically close, with a gap that vanishes with d at a rate that depends on the concentration function of the center of the Kolmogorov-Smirnov ball.

Massive multiple-input multiple-output (MIMO) communication is a promising technology for increasing spectral efficiency in wireless networks. Two of the main challenges massive MIMO systems face are degraded channel estimation accuracy due to pilot contamination and increase in computational load and hardware complexity due to the massive number of antennas. In this paper, we focus on the problem of channel estimation in massive MIMO systems, while addressing these two challenges: We jointly design the pilot sequences to mitigate the effect of pilot contamination and propose an analog combiner which maps the high number of sensors to a low number of RF chains, thus reducing the computational and hardware cost. We consider a statistical model in which the channel covariance obeys a Kronecker structure, and treat two special cases, corresponding to fully- and partially-separable correlations. We prove that under these models, the analog combiner design can be performed independently of the pilot sequences. Given the resulting combiner, we derive a closed-form expression for the optimal pilot sequences in the fully-separable case and suggest a greedy sum of ratio traces maximization (GSRTM) method for designing sub-optimal pilots in the partially-separable scenario. We demonstrate via simulations that our pilot design framework achieves lower mean squared error than the common pilot allocation framework previously considered for pilot contamination mitigation.

We revisit the problem of counting the number of directed graphs with a specified degree sequence, which was recently studied and solved by Barvinok using generating functions and convex duality techniques. We describe a systematic information-theoretic approach to this type of problems, based on studying invariant distributions and establishing suitable continuity and concentration properties. Our techniques recover and shed further light on Barvinok's solution, and may be applicable in other similar problems. As a simple example, we also apply our approach to estimating the number of undirected graphs with a given degree sequence. In particular, we show this number is approximately given by the square root of the number of associated directed graphs, whose input and output degree sequences are equal to that of the undirected graph.

We present a composite suite of technologies for spectral coexistence of existing communication and radar systems using the Xampling framework. For a stand-alone communication system, we consider a cognitive radio (CRo) that receives multiband signals with unknown carrier frequencies and directions of arrival, and demonstrate joint spectrum sensing via CompreSsed CArrier and Direction-ofarrival Estimation (CaSCADE) with an L-shaped configuration of two uniform linear arrays. For radars operating in bands with widespread spectral interference, we present an X-band prototype of cognitive sub-Nyquist multiple input multiple output (MIMO) radar (SUMMeR). The prototype allows sampling in both spatial and spectral domains at sub-Nyquist rates and cognitively transmits over multiple narrow subbands. Finally, we demonstrate Spectral Coexistence via Xampling (SpeCX) technology that shows joint operation of both - cognitive radio and cognitive monostatic radar - over a common spectrum. Our solutions to individual and joint operation of communication and radar systems supersede existing spectrum sharing technologies that require a compromise over performance of one of the systems.

With the emergence of Cognitive Radios (CRs), that aim at solving the spectrum scarcity issue, the traditional task of spectrum sensing has recently been revisited. Blind sub-Nyquist sampling and reconstruction methods of multiband signals have been proposed, alleviating the burden of both the analog and digital sides. In this work, we propose a new sub-Nyquist sampling system composed of sensors lying in a uniform linear array (ULA) that adopts some of the concepts of the Modulated Wideband Converter (MWC). Our system overcomes two practical issues of the MWC: the challenging choice of mixing functions which intentionally aliases the signal, and the introduction of the same sensor noise to all of the system channels. We provide two carrier frequencies recovery algorithms, and show how the signal can be reconstructed once these are estimated. We derive bounds for the minimal number of sensors and minimal sampling rate required for perfect signal reconstruction. Simulations show that for an equal number of channels or sensors and an identical sampling rate, our system outperforms the traditional MWC in terms of reconstruction performance.