We study a matrix completion problem which leverages a hierarchical structure of social similarity graphs as side information in the context of recommender systems. We assume that users are categorized into clusters, each of which comprises sub-clusters (or what we call “groups”). We consider a hierarchical stochastic block model that well respects practically-relevant social graphs and follows a low-rank rating matrix model. Under this setting, we characterize the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) as a function of the quality of graph side information (to be detailed) by proving sharp upper and lower bounds on the sample complexity. One important consequence of this result is that leveraging the hierarchical structure of similarity graphs yields a substantial gain in sample complexity relative to the one that simply identifies different groups without resorting to the relational structure across them. Another implication of the result is when the graph information is rich, the optimal sample complexity is proportional to the number of clusters, while it nearly stays constant as the number of groups in a cluster increases. We empirically demonstrate through extensive experiments that the proposed algorithm achieves the optimal sample complexity.

The information-theoretic secure exact-repair regenerating codes for distributed storage systems (DSSs) with parameters$(n,k=d,d,\ell)$are studied in this paper. We consider distributed storage systems with$n$nodes, in which the original data can be recovered from any subset of$k=d$nodes, and the content of any node can be retrieved from those of any$d$helper nodes. Moreover, we consider two secrecy constraints, namely, Type-I, where the message remains secure against an eavesdropper with access to the content of any subset of up to$\ell $nodes, and Type-II, in which the message remains secure against an eavesdropper who can observe the incoming repair data from all possible nodes to a fixed but unknown subset of up to$\ell $compromised nodes. Two classes of secure determinant codes are proposed for Type-I and Type-II secrecy constraints. Each proposed code can be designed for a range of per-node storage capacity and repair bandwidth for any system parameters. They lead to two achievable secrecy trade-offs, for Type-I and Type-II security.

We study a matrix completion problem that leverages a hierarchical structure of social similarity graphs as side information in the context of recommender systems. We assume that users are categorized into clusters, each of which comprises sub-clusters (or what we call “groups”). We consider a low-rank matrix model for the rating matrix, and a hierarchical stochastic block model that well respects practically-relevant social graphs. Under this setting, we characterize the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) as a function of the quality of graph side information (to be detailed) by proving sharp upper and lower bounds on the sample complexity. Furthermore, we develop a matrix completion algorithm and empirically demonstrate via extensive experiments that the proposed algorithm achieves the optimal sample complexity.

We consider a matrix completion problem that exploits social or item similarity graphs as side information. We develop a universal, parameter-free, and computationally efficient algorithm that starts with hierarchical graph clustering and then iteratively refines estimates both on graph clustering and matrix ratings. Under a hierarchical stochastic block model that well respects practically-relevant social graphs and a low-rank rating matrix model (to be detailed), we demonstrate that our algorithm achieves the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) that is derived by maximum likelihood estimation together with a lower-bound impossibility result. One consequence of this result is that exploiting the hierarchical structure of social graphs yields a substantial gain in sample complexity relative to the one that simply identifies different groups without resorting to the relational structure across them. We conduct extensive experiments both on synthetic and real-world datasets to corroborate our theoretical results as well as to demonstrate significant performance improvements over other matrix completion algorithms that leverage graph side information.

We consider the data shuffling problem in a distributed learning system, in which a master node is connected to a set of worker nodes, via a shared link, in order to communicate a set of files to the worker nodes. The master node has access to a database of files. In every shuffling iteration, each worker node processes a new subset of files, and has excess storage to partially cache the remaining files, assuming the cached files are uncoded. The caches of the worker nodes are updated every iteration, and they should be designed to satisfy any possible unknown permutation of the files in subsequent iterations. For this problem, we characterize the exact load-memory trade-off for worst-case shuffling by deriving the minimum communication load for a given storage capacity per worker node. As a byproduct, the exact load-memory trade-off for any shuffling is characterized when the number of files is equal to the number of worker nodes. We propose a novel deterministic coded shuffling scheme, which improves the state of the art, by exploiting the cache memories to create coded functions that can be decoded by several worker nodes. Then, we prove the optimality of our proposed scheme by deriving a matching lower bound and showing that the placement phase of the proposed coded shuffling scheme is optimal over all shuffles.

We consider the data shuffling problem, in which a master node is connected to a set of worker nodes, via a shared link, in order to communicate a set of files to the worker nodes. The master node has access to a database of files. In every shuffling iteration, each worker node processes a new subset of files, and has excess storage to partially cache the remaining files. We characterize the exact rate-memory trade-off for the worst-case shuffling under the assumption that cached files are uncoded, by deriving the minimum communication rate for a given storage capacity per worker node. As a byproduct, the exact rate-memory trade-off for any random shuffling is characterized when the number of files is equal to the number of worker nodes. We propose a novel deterministic and systematic coded shuffling scheme, which improves the state of the art. Then, we prove the optimality of our proposed scheme by deriving a matching lower bound and showing that the placement phase of the proposed coded shuffling scheme is optimal over all shuffles.

We explore an active top-$K$ ranking problem based on pairwise comparisons that are collected possibly in a sequential manner as per our design choice. We consider two settings: (1) top-$K$ sorting in which the goal is to recover the top-$K$ items in order out of $n$ items; (2) top-$K$ partitioning where only the set of top-$K$ items is desired. Under a fairly general model which subsumes as special cases various models (e.g., Strong Stochastic Transitivity model, BTL model and uniform noise model), we characterize upper bounds on the sample size required for top-$K$ sorting as well as for top-$K$ partitioning. As a consequence, we demonstrate that active ranking can offer significant multiplicative gains in sample complexity over passive ranking. Depending on the underlying stochastic noise model, such gain varies from around $\frac{\log n}{\log \log n}$ to $\frac{ n^2 \log n }{\log \log n}$. We also present an algorithm that is applicable to both settings.

We consider the problem of optimizing the performance of a cooperative cognitive radio user subject to constraints on the quality-of-service (QoS) of the primary user (PU). In particular, we design the probabilistic admission control parameter of the PU packets in the secondary user (SU) relaying queue and the randomized service parameter at the SU under non-work-conserving (non-WC) and WC cooperation policies. In the non-WC policy, two constrained optimization problems are formulated; the first problem is maximizing the SU throughput while the second problem is minimizing the SU average delay. In both problems, a constraint is imposed on the maximum allowable average delay of the PU. We show the equivalence of the two problems and develop a low-complexity line search algorithm to find the optimal parameters. Subsequently, the idea of optimizing the SU average delay is developed for the more complex WC policy, for its superior resource utilization and performance. Due to the sheer complexity of this optimization problem, we formulate another problem whose solution yields a suboptimal upper bound on the optimal SU delay. Afterwards, a practical WC-policy-based algorithm is designed in order to closely approach the optimal value of the SU delay. We show, through numerical results, that the proposed cooperation policies represent the best compromise between enhancing the SU QoS and satisfying the PU QoS requirements. Furthermore, the superior performance of the suboptimal WC policy over the non-WC policy is illustrated. Finally, the merits of the WC-policy-based algorithm are demonstrated through extensive simulations.

In this paper, we characterize the total degrees of freedom (DoFs) of the full-duplex asymmetric multiple-input multiple- output (MIMO) three-way channel. Each node has a separate-antenna full-duplex MIMO transceiver with a different number of antennas, where each antenna can be configured for either signal transmission or reception. We study this system under two message configurations; the first configuration is when each node has two unicast messages to be delivered to the two other nodes, while the second configuration is when each node has two unicast messages as well as one broadcast message to be delivered to the two other nodes. For each configuration, we first derive upper bounds on the total DoF of the system. Cut-set bounds in conjunction with genie-aided bounds are derived to characterize the achievable total DoF. Afterward, we analytically derive the optimal number of transmit and receive antennas at each node to maximize the total DoF of the system, subject to the total number of antennas at each node. Finally, the achievable schemes for each configuration are constructed. The proposed schemes are mainly based on zero-forcing and null-space transmit beamforming. We show that the derived outer and inner bounds on the total DoF are tight for each message configuration.

In this paper, we characterize the asymmetric total degrees of freedom (DoF) of a multiple-input multiple-output (MIMO) 3-way channel. Each node has a separate-antenna full-duplex MIMO transceiver with a different number of antennas, where each antenna can be configured for either signal transmission or reception. Each node has two unicast messages to be delivered to the two other nodes. We first derive upper bounds on the total DoF of the system. Cut-set bounds in conjunction with genie-aided bounds are derived to characterize the achievable total DoF. Afterwards, we analytically derive the optimal number of transmit and receive antennas at each node to maximize the total DoF of the system, subject to the total number of antennas at each node. Finally, the achievable schemes are constructed. The proposed schemes are mainly based on zero-forcing and null-space transmit beamforming.

We study the problem of optimizing the performance of cognitive radio users with opportunistic real-time applications subject to primary users quality-of-service (QoS) constraints. Two constrained optimization problems are formulated; the first problem is maximizing the secondary user throughput while the second problem is minimizing the secondary user average delay, subject to a common constraint on the primary user average delay. In spite of the complexity of the optimization problems, due to their non-convexity, we transform the first problem into a set of linear programs and the second problem into a set of quasiconvex optimization problems. We prove that both problems are equivalent with identical feasible sets and optimal solutions. We show, through numerical results, that the proposed cooperation policy represents the best compromise between enhancing the secondary users QoS and satisfying the primary users QoS requirements.

In this paper, we study the problem of cooperative communications in cognitive radio systems where the secondary user has limited relaying room for the overheard primary packets. More specifically, we characterize the stable throughput region of a cognitive radio network with a finite relaying buffer at the secondary user. Towards this objective, we formulate a constrained optimization problem for maximizing the secondary user throughput while guaranteeing the stability of the primary user queue. We consider a general cooperation policy where the packet admission and queue selection probabilities, at the secondary user, are both dependent on the state (length) of the finite relaying buffer. Despite the sheer complexity of the optimization problem, attributed to its non-convexity, we transform it to a linear program. Our numerical results reveal a number of valuable insights, e.g., it is always mutually beneficial to cooperate in delivering the primary packets in terms of expanding the stable throughput region. In addition, the stable throughput region of the system, compared to the case of infinite relaying queue capacity, marginally shrinks for limited relaying queue capacity.

In this paper, we investigate the problem of minimizing the frame completion delay for Instantly Decodable Network Coding (IDNC) in relay-assisted wireless multicast networks. We first propose a packet recovery algorithm in the single relay topology which employs generalized IDNC instead of strict IDNC previously proposed in the literature for the same relay-assisted topology. This use of generalized IDNC is supported by showing that it is a super-set of the strict IDNC scheme, and thus can generate coding combinations that are at least as efficient as strict IDNC in reducing the average completion delay. We then extend our study to the multiple relay topology and propose a joint generalized IDNC and relay selection algorithm. This proposed algorithm benefits from the reception diversity of the multiple relays to further reduce the average completion delay in the network. Simulation results show that our proposed solutions achieve much better performance compared to previous solutions in the literature.