Spectral clustering is a celebrated algorithm that partitions objects based on pairwise similarity information. While this approach has been successfully applied to a variety of domains, it comes with limitations. The reason is that there are many other applications in which only multi-way similarity measures are available. This motivates us to explore the multi-way measurement setting. In this work, we develop two algorithms intended for such setting: Hypergraph Spectral Clustering (HSC) and Hypergraph Spectral Clustering with Local Refinement (HSCLR). Our main contribution lies in performance analysis of the poly-time algorithms under a random hypergraph model, which we name the weighted stochastic block model, in which objects and multi-way measures are modeled as nodes and weights of hyperedges, respectively. Denoting by n the number of nodes, our analysis reveals the following: (1) HSC outputs a partition which is better than a random guess if the sum of edge weights (to be explained later) is Ω(n); (2) HSC outputs a partition which coincides with the hidden partition except for a vanishing fraction of nodes if the sum of edge weights is ω(n); and (3) HSCLR exactly recovers the hidden partition if the sum of edge weights is on the order of n log(n). Our results improve upon the state of the arts recently established under the model and they firstly settle the order-wise optimal results for the binary edge weight case. Moreover, we show that our results lead to efficient sketching algorithms for subspace clustering, a computer vision application. Lastly, we show that HSCLR achieves the information-theoretic limits for a special yet practically-relevant model, thereby showing no computational barrier for the case.

We establish the degrees of freedom (DoF) of the two-user X-channel with delayed channel knowledge at transmitters [i.e., delayed channel state information at the transmitters (CSIT)], assuming linear coding strategies at the transmitters. We derive a new upper bound and characterize the linear DoF of this network to be 6/5. The converse builds upon our development of a general lemma that shows that, if two distributed transmitters employ linear strategies, the ratio of the dimensions of received linear subspaces at the two receivers cannot exceed 3/2, due to delayed CSIT. As a byproduct, we also apply this general lemma to the three-user interference channel with delayed CSIT, thereby deriving a new upper bound of 9/7 on its linear DoF. This is the first bound that captures the impact of delayed CSIT on the DoF of this network, under the assumption of linear encoding strategies.

Developing a computer vision-based algorithm for identifying dangerous vehicles requires a large amount of labeled accident data, which is difficult to collect in the real world. To tackle this challenge, we first develop a synthetic data generator built on top of a driving simulator. We then observe that the synthetic labels that are generated based on simulation results are very noisy, resulting in poor classification performance. In order to improve the quality of synthetic labels, we propose a new label adaptation technique that first extracts internal states of vehicles from the underlying driving simulator, and then refines labels by predicting future paths of vehicles based on a well-studied motion model. Via real-data experiments, we show that our dangerous vehicle classifier can reduce the missed detection rate by at least 18.5% compared with those trained with real data when time-to-collision is between 1.6s and 1.8s.

In this paper, we propose an opportunistic downlink interference alignment (ODIA) for interference-limited cellular downlink, which intelligently combines user scheduling and downlink IA techniques. The proposed ODIA not only efficiently reduces the effect of inter-cell interference from other-cell base stations (BSs) but also eliminates intra-cell interference among spatial streams in the same cell. We show that the minimum number of users required to achieve a target degrees-of-freedom can be fundamentally reduced, i.e., the fundamental user scaling law can be improved by using the ODIA, compared with the existing downlink IA schemes. In addition, we adopt a limited feedback strategy in the ODIA framework, and then analyze the number of feedback bits required for the system with limited feedback to achieve the same user scaling law of the ODIA as the system with perfect channel state information. We also modify the original ODIA in order to further improve the sum-rate, which achieves the optimal multiuser diversity gain, i.e., log log N, per spatial stream even in the presence of downlink inter-cell interference, where N denotes the number of users in a cell. Simulation results show that the ODIA significantly outperforms existing interference management techniques in terms of sum rate in realistic cellular environments. Note that the ODIA operates in a non-collaborative and decoupled manner, i.e., it requires no information exchange among BSs and no iterative beamformer optimization between BSs and users, thus leading to an easier implementation.

This paper is concerned with jointly recovering n node variables {x _i } _1≤i≤n from a collection of pairwise difference measurements. Imagine we acquire a few observations taking the form of x _i - x _j ; the observation pattern is represented by a measurement graph G with an edge set ℰ, such that x _i -x _j is observed if and only if (i, j) ε ℰ. To account for noisy measurements in a general manner, we model the data acquisition process by a set of channels with given input/output transition measures. Employing information-theoretic tools applied to channel decoding problems, we develop a unified framework to characterize the fundamental recovery criterion, which accommodates general graph structures, alphabet sizes, and channel transition measures. In particular, our results isolate a family of minimum channel divergence measures to characterize the degree of measurement corruption, which together with the size of the minimum cut of G dictates the feasibility of exact information recovery. For various homogeneous graphs, the recovery condition depends almost only on the edge sparsity of the measurement graph irrespective of other graphical metrics; alternatively, the minimum sample complexity required for these graphs scales like (n log n)/(Hel _1/2 ^min ) for certain information metric Hel _1/2 ^min defined in the main text, as long as the alphabet size is not super-polynomial in n. We apply our general theory to three concrete applications, including the stochastic block model, the random corruption model, and the haplotype assembly problem. Our theory leads to orderwise tight recovery conditions for all these scenarios.

An uplink-downlink two-cell cellular network is studied in which the first base station (BS) with M ₁ antennas receives independent messages from its N ₁ serving users, while the second BS with M ₂ antennas transmits independent messages to its N ₂ serving users. That is, the first and second cells operate as uplink and downlink, respectively. Each user is assumed to have a single antenna. Under this uplink-downlink setting, the sum degrees of freedom (DoFs) is completely characterized as the minimum of (N ₁ N ₂ + min(M ₁ , N ₁ )(N ₁ - N ₂ ) ⁺ + min(M ₂ , N ₂ )(N ₂ - N ₁ ) ⁺ )/ max(N ₁ , N ₂ ), M ₁ + N ₂ , M ₂ + N ₁ , max(M ₁ , M ₂ ), and max(N ₁ , N ₂ ), where a ⁺ denotes max(0, a). The result demonstrates that, for a broad class of network configurations, operating one of the two cells as uplink and the other cell as downlink can strictly improve the sum DoF compared with the conventional uplink or downlink operation, in which both cells operate as either uplink or downlink. The DoF gain from such uplink-downlink operation is further shown to be achievable for heterogeneous cellular networks having hotspots and with delayed channel state information.