A rank-$r$ matrix $X \in \mathbb{R}^{m \times n}$ can be written as a product $U V^\top$, where $U \in \mathbb{R}^{m \times r}$ and $V \in \mathbb{R}^{n \times r}$. One could exploit this observation in optimization: e.g., consider the minimization of a convex function $f(X)$ over rank-$r$ matrices, where the set of low-rank matrices is modeled via $UV^\top$. Though such parameterization reduces the number of variables and is more computationally efficient (of particular interest is the case $r \ll \min\{m, n\}$), it comes at a cost: $f(U V^\top)$ becomes a nonconvex function w.r.t. $U$ and $V$. We study such parameterization on generic convex objectives $f$ and focus on first-order, gradient descent algorithms. We propose the bifactored gradient descent (\textttBFGD) algorithm, an efficient first-order method that operates directly on the $U, V$ factors. We show that when $f$ is (restricted) smooth, \textttBFGD has local sublinear convergence; when $f$ is both (restricted) smooth and (restricted) strongly convex, it has local linear convergence. For several applications, we provide simple and efficient initialization schemes that provide initial conditions, good enough for the above convergence results to hold, globally. Extensive experimental results support our arguments that \textttBFGD is an efficient and accurate nonconvex method, compared to state-of-the-art approaches.

We consider the non-square matrix sensing problem, under restricted isometry property (RIP) assumptions. We focus on the non-convex formulation, where any rank-r matrix $X ∈R^m x n$ is represented as $UV^T$, where $U ∈R^m x r$ and $V ∈R^n x r$. In this paper, we complement recent findings on the non-convex geometry of the analogous PSD setting [5], and show that matrix factorization does not introduce any spurious local minima, under RIP.

We consider the problem of Robust PCA in the fully and partially observed settings. Without corruptions, this is the well-known matrix completion problem. From a statistical standpoint this problem has been recently well-studied, and conditions on when recovery is possible (how many observations do we need, how many corruptions can we tolerate) via polynomial-time algorithms is by now understood. This paper presents and analyzes a non-convex optimization approach that greatly reduces the computational complexity of the above problems, compared to the best available algorithms. In particular, in the fully observed case, with $r$ denoting rank and $d$ dimension, we reduce the complexity from $O(r^2d^2\log(1/\epsilon))$ to $O(rd^2\log(1/\epsilon))$ -- a big savings when the rank is big. For the partially observed case, we show the complexity of our algorithm is no more than $O(r^4d\log(d)\log(1/\epsilon))$. Not only is this the best-known run-time for a provable algorithm under partial observation, but in the setting where $r$ is small compared to $d$, it also allows for near-linear-in-$d$ run-time that can be exploited in the fully-observed case as well, by simply running our algorithm on a subset of the observations.

In this paper we consider the collaborative ranking setting: a pool of users each provides a set of pairwise preferences over a small subset of the set of d possible items; from these we need to predict each user’s preferences for items s/he has not yet seen. We do so via fitting a rank r score matrix to the pairwise data, and provide two main contributions: (a) We show that an algorithm based on convex optimization provides good generalization guarantees once each user provides as few as O(r \log^2 d) pairwise comparisons — essentially matching the sample complexity required in the related matrix completion setting (which uses actual numerical as opposed to pairwise information), and also matching a lower bound we establish here. (b) We develop a large-scale non-convex implementation, which we call AltSVM, which trains a factored form of the matrix via alternating minimization (which we show reduces to alternating SVM problems), and scales and parallelizes very well to large problem settings. It also outperforms common baselines on many moderately large popular collaborative filtering datasets in both NDCG and other measures of ranking performance.

We introduce an opportunistic interference mitigation (OIM) protocol, where a user scheduling strategy is utilized in K-cell uplink networks with time-invariant channel coefficients and base stations (BSs) having M antennas. Each BS opportunistically selects a set of users who generate the minimum interference to the other BSs. Two OIM protocols are shown according to the number of simultaneously transmitting users per cell, S: opportunistic interference nulling (OIN) and opportunistic interference alignment (OIA). Then, their performance is analyzed in terms of degrees-of-freedom (DoFs). As our main result, it is shown that KM DoFs are achievable under the OIN protocol with M selected users per cell, if the total number of users in a cell, N, scales at least as SNR(K-1)M. Similarly, it turns out that the OIA scheme with S((K-1)S. These results indicate that there exists a trade-off between the achievable DoFs and the minimum required N. By deriving the corresponding upper bound on the DoFs, it is shown that the OIN scheme is DoF-optimal. Finally, numerical evaluation, a two-step scheduling method, and the extension to multi-carrier scenarios are shown.

We introduce a distributed opportunistic scheduling (DOS) strategy, based on two pre-determined thresholds, for uplink K-cell networks with time-invariant channel coefficients. Each base station (BS) opportunistically selects a mobile station (MS) who has a large signal strength of the desired channel link among a set of MSs generating a sufficiently small interference to other BSs. Then, performance on the achievable throughput scaling law is analyzed. As our main result, it is shown that the achievable sum-rate scales as K log(SNR log N) in a high signal-to-noise ratio (SNR) regime, if the total number of users in a cell, N, scales faster than SNRK-1/1-εfor a constant ε∈(0,1). This result indicates that the proposed scheme achieves the multiuser diversity gain as well as the degrees-of-freedom gain even under multi-cell environments. Simulation results show that the DOS provides a better sum-rate throughput over conventional schemes.

We consider an ad hoc indoor device tracking problem where a user device has no knowledge of map and infrastructure. Since it does not have any information of reference points, the user device finds relative location of its target device. In fact, relative location, which can be described by direction and distance, is sufficient for the user device to track and approach the target device. However, indoor multipath environment and a single antenna of the device are obstacles to measuring direction using direction-of-arrival (DOA). Instead, if the user or the target device is moving, then, by fusing distance measurements and sensor information, the user device can estimate direction and thus calculate the relative location of the target. We show that the relative location can be calculated by trilateration in some cases. As a flexible and adaptable method, we also employ a simultaneous localization and mapping (SLAM)-based method using a particle filter (PF).We evaluate the ad hoc device tracking in some environments by simulation.

In this paper, we study degrees of freedom for the K-User multiple-input multiple-output (MIMO)-interference channel (IFC) with constant channel coefficients. In this channel, we investigate how many total number of transmit antennas, M1+ M2+ ¿ + MK, are required in minimum to achieve di= 1,¿i degrees of freedom when all receivers have N = 2 antennas, which is a downlink communication scenario. To answer this question, we propose a new interference alignment scheme based on intersection subspace property of the vector space. The proposed interference alignment scheme can be easily generalized regardless of the number of users. In addition, we investigate degrees of freedom for the partially connected MIMOIFC where some arbitrary interfering links are disconnected due to the large path loss or deep fades. In this channel model, we examine how these disconnected links are considered on designing the beamforming vectors for interference alignment.

We analyze performance-complexity tradeoffs of rateless codes over noisy symmetric channels. Unlike in erasure channels, the decoder for such codes needs to use all received symbols in noisy channels because each of them have some information about the transmitted message. To reduce the complexity, the receiver can discard some unreliable symbols, but it must receive more symbols due to the lost information. This results in a performance-complexity tradeoff. We also consider another scenario where a rateless code is concatenated with a fixed-rate code, which is typically used in practice, e.g., in [1]. The fixed-rate code provides a soft-decision decoding and only correctly decoded blocks are used in the rateless code decoder. If some soft information of error-detected blocks is also used, the receiver can decode the message with less received symbols at the expense of increased processing. This results in another type of performance-complexity tradeoff. For these scenarios, we find the optimal tradeoffs and show sub-optimal tradeoffs achievable by practical rateless codes.