We introduce the triangle-densest-k-subgraph problem (TDkS) for undirected graphs: given a size parameter k, compute a subset of k vertices that maximizes the number of induced triangles. The problem corresponds to the simplest generalization of the edge-based densest-k-subgraph problem (DkS) to the case of higher-order network motifs. We prove that TDkS is NP-hard and is not amenable to efficient approximation, in the worst-case. By judiciously exploiting the structure of the problem, we propose a relaxation algorithm for the purpose of obtaining high-quality, sub-optimal solutions. Our approach utilizes the fact that the cost function of TDkS is submodular to construct a convex relaxation for the problem based on the Lovasz extension for submodular functions. We ´ demonstrate that our approaches attain state-of-the-art performance on real-world graphs and can offer substantially improved exploration of the optimal density-size curve compared to sophisticated approximation baselines for DkS. We use document summarization to showcase why TDkS is a useful generalization of DkS

Given an unweighted, undirected, and simple graph, the Densest k-Subgraph (DkS) problem aims to find a subgraph of k vertices that has the maximum average induced degree. In this paper, we consider an equivalent reformulation of the DkS problem via diagonal loading. On relaxing the combinatorial constraint of the reformulated problem, we show that the resulting non-convex, continuous relaxation is tight under certain conditions by leveraging an extension of the Motzkin-Straus theorem. We utilize two projection-free approaches to solve the relaxed problem: one based on the Frank-Wolfe algorithm and the other on explicit constraint parameterization. We compare their performance to state-of-the-art baselines across various benchmarks. Our empirical results show that the Frank-Wolfe-based algorithm proposed in this paper outperforms existing baselines in terms of subgraph density and computational complexity.

Signal Alignment has been recently introduced as a simple and effective means of communicating under powerful and unpredictable (e.g., intermittent) interference. Signal alignment uses repetition coding at the transmitter and canonical correlation analysis (CCA) at the (multi-antenna) receiver to synchronize with and decode the signal of interest. CCAbased synchronization works even in the face of adverse interference, where classical synchronization methods fail; but this requires solving the CCA problem repeatedly, in a sliding window fashion, which is computationally demanding. This paper poses the associated adaptive CCA problem and proposes two computationally efficient and scalable algorithms for solving it. These work by leveraging algebraic properties stemming from shift structures and different reformulations of the batch CCA problem. This enables real-time application of signal alignment as well as applications in other areas where adaptive CCA makes sense. The algorithms are validated in judicious experiments showcasing the computational benefits afforded by the proposed algorithms.

Hybrid automatic repeat request (HARQ) protocols use forward error correction and detection to trigger additional transmissions, until a packet is correctly decoded. Type-I HARQ (HARQ-I) uses packet retransmission and so-called chase combining of the received packets. HARQ protocols are widely used at the radio link / transport layer of wireless standards like 5G and WiFi to guarantee practically error-free end-to-end message delivery. Existing HARQ protocols are not designed to handle strong interference, which must be normally dealt with at the physical layer. On the other hand, recent work has shown that, with the right kind of multi-antenna signal processing at the receiver, based on canonical correlation analysis (CCA), retransmissions can be leveraged to eliminate interference. This creates an opportunity for synergistic cross-layer design, where a modified HARQ protocol will also excise interference. This paper proposes combining CCA-based interference excision and HARQ-I. The resulting protocol uses CCA in place of chase combining for interference immunity and better performance at low signal to noise ratios, while HARQ-I controls how many retransmissions are needed on the fly. The combination offers the best of both worlds and is backwards-compatible with the HARQ-I standard. Simulations for a 5G scenario with Rayleigh fading and one interferer that is 20 dB above the noise floor indicate impressive gains in terms of throughput and delay relative to standard HARQ-I with chase combining.

This paper introduces a novel method for decoding uplink messages in Internet of Things (IoT) networks that utilize packet repetition, such as Sigfox and LoRa. These protocols use packet repetition at different pseudo-random frequency hops to avoid collisions and channel fades, but they do not coherently combine signals across these random (a priori unknown) hops. This paper introduces a novel frequency alignment strategy that leverages the frequency-hopped repetition structure to decode signals at lower transmission power levels without requiring channel state information, providing a significant advantage over techniques that rely on channel estimates. The proposed approach is validated through extensive simulations and real-world experiments examining its effectiveness in both single-user and multi-user environments under conditions of high system load and interference. The results demonstrate that the proposed approach not only enhances the performance and reliability of IoT networks but also contributes to more energy-efficient communication for IoT Low Power Wide Area Networks (LPWANs), thus offering a substantial advancement in dependable IoT communications.

Dense subgraph discovery (DSD) is a key primitive in graph mining that typically deals with extracting cliques and near-cliques. In this paper, we revisit the optimal quasi-clique (OQC) formulation for DSD and establish that it is NP--hard. In addition, we reveal the hitherto unknown property that OQC can be used to explore the entire spectrum of densest subgraphs of all distinct sizes by appropriately varying a single hyperparameter, thereby forging an intimate link with the classic densest-k-subgraph problem (DkS). We corroborate these findings on real-world graphs by applying the simple greedy algorithm for OQC with improved hyperparameter tuning, to quickly generate high-quality approximations of the size-density frontier. Our findings indicate that OQC not only extracts high quality (near)-cliques, but also large and loosely-connected subgraphs that exhibit well defined local community structure. The latter discovery is particularly intriguing, since OQC is not explicitly geared towards community detection.

We consider the problem of learning smooth multivariate probability density functions. We invoke the canonical decomposition of multivariate functions and we show that if a joint probability density function admits a truncated Fourier series representation, then the classical univariate Fejér-Riesz Representation Theorem can be used for learning bona fide joint probability density functions. We propose a scalable, flexible, and direct framework for learning smooth multivariate probability density functions even from potentially incomplete datasets. We demonstrate the effectiveness of the proposed framework by comparing it to several popular state-of-the-art methods.

In this paper we revisit a recently proposed underlay communication scheme which relies on repetition of the secondary signal at the transmitter and canonical correlation analysis CCA at the (multi-antenna) receiver. In this setting, CCA can provably extract the underlay signal in the presence of potentially strong and time-varying primary interference, without any channel knowledge. At its core, the concept relies on embedding the signal of interest in two distinct mixtures or "views", thus exploiting signal alignment as opposed to interference alignment, which is far less practical. In earlier work, the signal of interest was treated as analog for the purposes of CCA, and projected onto the finite alphabet after extracting it from interference. In this contribution we incorporate a binary symbol constraint directly into the CCA optimization formulation. We show two surprising results: that the resulting binary signal alignment problem can be optimally solved in polynomial time, and that a linear-time two-step solution is very close to the optimal one, for all practical purposes.

Tensor completion (TC) refers to restoring the missing entries in a given tensor by making use of the low-rank structure. Most existing algorithms have excellent performance in Gaussian noise or impulsive noise scenarios. Generally speaking, the Frobenius-norm-based methods achieve excellent performance in additive Gaussian noise, while their recovery severely degrades in impulsive noise. Although the algorithms using the$\ell_{p}$-norm ($0<p<2$) or its variants can attain high restoration accuracy in the presence of gross errors, they are inferior to the Frobenius-norm-based methods when the noise is Gaussian-distributed. Therefore, an approach that is able to perform well in both Gaussian noise and impulsive noise is desired. In this work, we use a capped Frobenius norm to restrain outliers, which corresponds to a form of the truncated least-squares loss function. The upper bound of our capped Frobenius norm is automatically updated using normalized median absolute deviation during iterations. Therefore, it achieves better performance than the$\ell_{p}$-norm with outlier-contaminated observations and attains comparable accuracy to the Frobenius norm without tuning parameter in Gaussian noise. We then adopt the half-quadratic theory to convert the nonconvex problem into a tractable multivariable problem, that is, convex optimization with respect to (w.r.t.) each individual variable. To address the resultant task, we exploit the proximal block coordinate descent (PBCD) method and then establish the convergence of the suggested algorithm. Specifically, the objective function value is guaranteed to be convergent while the variable sequence has a subsequence converging to a critical point. Experimental results based on real-world images and videos exhibit the superiority of the devised approach over several state-of-the-art algorithms in terms of recovery performance. MATLAB code is available at https://github.com/Li-X-P/Code-of-Robust-Tensor-Completion.

Patient enrollment is critical to the success of a clinical trial. In practice, before launching a trial, one of the top priorities is to predict the enrollment rate for different countries, so that one can select clinical sites from the countries with the highest enrollment rates to accelerate patient recruitment. However, based on the limited trial information, estimating the enrollment rate is still a challenge. To deal with this problem, we adopt a very recent tensor factorization approach that aims to approximate the joint Cumulative Distribution Function (CDF) of trial enrollment data. We can always sketch a multivariate CDF in terms of multidimensional empirical cumulative probability array, i.e., a finite grid-sampled CDF tensor, and introduce a low-rank parametrization by a Canonical Polyadic Decomposition (CPD) model. The proposed model is unassuming of the structure of the data and identifiable under mild conditions by virtue of the uniqueness of CPD. At the same time, it affords both efficient sample likelihood estimation and closed-form inference. Such model can be leveraged for reliable enrollment estimation, delivering probability estimates of a specific trial meeting an expected enrollment rate or probability estimates of being within a certain interval, as well as country recommendation. Experimental results demonstrate an improved performance of the proposed method in the enrollment rate prediction task over the best baselines by up to 12.2% in mean squared error on a real country-level trial dataset, while also offering direct means of quantifying uncertainty in the predictions based on the fitted model. The improved performance and versatility highlight the societal and financial benefits of the proposed approach, which could be transformational in modern healthcare.

Antenna arrays with a large number of sensors are becoming increasingly common in radio astronomy. This has motivated the development of array signal processing tools for high-resolution imaging that exploit source signal properties such as sparsity and spectral or temporal variability. We propose a new multi-frequency covariance matrix model for radio astronomical imaging that exploits spectral variability of the astronomical sources. We show that tensor decomposition methods can be used to compute high-resolution images of astronomical scenes that comprise Q point sources. In this context, tensor decomposition can reduce the problem to simpler single-point source imaging problems. We also explain how canonical correlation analysis can be used to mitigate or even altogether remove the effect of (unknown) narrowband interference sources, which is a key challenge in this context.

Most existing studies on linear bandits focus on a one-dimensional characterization of the overall system. While being representative, this formulation may fail to model applications with high-dimensional but favorable structures, such as the low-rank tensor representation for recommender systems. To address this limitation, this work studies a general tensor bandits model, where actions and system parameters are represented by tensors as opposed to vectors, and we particularly focus on the case that the unknown system tensor is low-rank. A novel bandit algorithm, coined TOFU (Tensor Optimism in the Face of Uncertainty), is developed. TOFU first leverages flexible tensor regression techniques to estimate low-dimensional subspaces associated with the system tensor. These estimates are then utilized to convert the original problem to a new one with norm constraints on its system parameters. Lastly, a norm-constrained bandit subroutine is adopted by TOFU, which utilizes these constraints to avoid exploring the entire high-dimensional parameter space. Theoretical analyses show that TOFU improves the best-known regret upper bound by a multiplicative factor that grows exponentially in the system order. A novel performance lower bound is also established, which further corroborates the efficiency of TOFU.

Given a tensor that captures temporal data, such as (user, item, time), the way that we set the granularity of the “time” mode can make or break our analysis of the data. If we set the granularity to be extremely fine, we end up with a very sparse and high-rank tensor which is essentially incompatible with what virtually all tensor decomposition models expect, i.e., tensors with low-rank structure, which can be expressed in some form of factorization. Traditionally, this problem has been avoided by setting the granularity of the “time” to a “reasonable” aggregation (say hourly or daily intervals), an approach which has certainly served tensor analysis of temporal methods well so far. However, such an approach requires tedious trial- and-error experimentation across a number of such fixed aggregations, where typically the one that provides the most sensible results is retained, and furthermore it is arbitrary, since the optimal aggregation over time need not necessarily be uniform. In our work, we directly tackle this problem. We introduce Harvester, the first principled factorization-based approach which seeks to identify the best temporal granularity of a given tensor. Unlike existing methods which follow a greedy approach, Harvester leverages multiple aggregated views of the tensor, and a carefully-designed optimization problem, in order to uncover an aggregation of a tensor which has a “good” structure for factor analysis or a downstream task. We extensively evaluate Harvester on synthetic and real data, and demonstrate that it consistently produces tensors of very high quality, compared to the state-of-the-art, across the board for a number of different popular quality measures that have been used by the community.

We introduce the triangle-densest-K-subgraph problem (TDKS) for undirected graphs: given a size parameter K, compute a subset of K vertices that maximizes the number of induced triangles. The problem corresponds to the simplest generalization of the edge based densest-K-subgraph problem (DKS) to the case of higher-order network motifs. We prove that TDKS is NP-hard and is not amenable to efficient approximation, in the worst-case. By judiciously exploiting the structure of the problem, we propose a relaxation algorithm for the purpose of obtaining high-quality, sub-optimal solutions. Our approach utilizes the fact that the cost function of TDKS is submodular to construct a convex relaxation for the problem based on the Lovász extension for submodular functions. We demonstrate that our approaches attain state-of-the-art performance on real-world graphs and can offer substantially improved exploration of the optimal density-size curve compared to sophisticated approximation baselines for DKS. We use document summarization to showcase why TDKS is a useful generalization of DKS.

Node embedding is the task of extracting concise and informative representations of certain entities that are connected in a network. Various real-world networks include information about both node connectivity and certain node attributes, in the form of features or time-series data. Modern representation learning techniques employ both the connectivity and attribute information of the nodes to produce embeddings in an unsupervised manner. In this context, deriving embeddings that preserve the geometry of the network and the attribute vectors would be highly desirable, as they would reflect both the topological neighborhood structure and proximity in feature space. While this is fairly straightforward to maintain when only observing the connectivity or attribute information of the network, preserving the geometry of both types of information is challenging. A novel tensor factorization approach for node embedding in attributed networks is proposed in this paper, that preserves the distances of both the connections and the attributes. Furthermore, an effective and lightweight algorithm is developed to tackle the learning task and judicious experiments with multiple state-of-the-art baselines suggest that the proposed algorithm offers significant performance improvements in downstream tasks.

The ever-growing demands on wireless connectivity, especially with the emergence of various data-intensive low-latency applications, require novel multiplexing solutions capable of reliably supporting high rates at low latency. Non-orthogonal time division duplex (TDD) coupled with multiuser detection can meet these emerging needs, provided that accurate channel state information is available. This paper proposes a new pilot-free TDD frame structure that allows designing highly effective multiuser decoders and precoders for uplink and downlink multicell systems, in an unsupervised manner. The key idea is that each user repeats and permutes its uplink data using a pre-assigned permutation code. Invoking canonical correlation analysis (CCA) at the serving BS on the two deinterleaved uplink blocks yields high quality CCA-based beamformers capable of both recovering the uplink and precoding the downlink user signals in a way that effectively mitigates interference. The paper includes a pilotless synchronization framework that leverages CCA to recover the timing and frequency offsets in an asynchronous multiuser MIMO setup, without using pilots. Simulations are used to study the performance of the proposed approach on a large-scale network with multiple users and cells, while laboratory experiments with a small-scale network of software radios are used to demonstrate that the approach works well in practice under common hardware imperfections.

Functional magnetic resonance imaging (fMRI) is one of the most popular methods for studying the human brain. Task-related fMRI data processing aims to determine which brain areas are activated when a specific task is performed and is usually based on the Blood Oxygen Level Dependent (BOLD) signal. The background BOLD signal also reflects systematic fluctuations in regional brain activity which are attributed to the existence of resting-state brain networks. We propose a new fMRI data generating model which takes into consideration the existence of common task-related and resting-state components. We first estimate the common task-related temporal component, via two successive stages of generalized canonical correlation analysis and, then, we estimate the common task-related spatial component, leading to a task-related activation map. The experimental tests of our method with synthetic data reveal that we are able to obtain very accurate temporal and spatial estimates even at very low Signal to Noise Ratio (SNR), which is usually the case in fMRI data processing. The tests with real-world fMRI data show significant advantages over standard procedures based on General Linear Models (GLMs).

Graph matching, the problem of aligning a pair of graphs so as to minimize their edge disagreements, has received widespread attention owing to its broad spectrum of applications in data science. As the problem is NP–hard in the worst-case, a variety of approximation algorithms have been proposed for obtaining high quality, suboptimal solutions. In this article, we approach the task of designing an efficient polynomial-time approximation algorithm for graph matching from a previously unconsidered perspective. Our key result is that graph matching can be formulated as maximizing a monotone, supermodular set function subject to matroid intersection constraints. We leverage this fact to apply a discrete optimization variant of the minorization-maximization algorithm which exploits supermodularity of the objective function to iteratively construct and maximize a sequence of global lower bounds on the objective. At each step, we solve a maximum weight matching problem in a bipartite graph. Differing from prior approaches, the algorithm exploits the combinatorial structure inherent in the problem to generate a sequence of iterates featuring monotonically non-decreasing objective value while always adhering to the combinatorial matching constraints. Experiments on real-world data demonstrate the empirical effectiveness of the algorithm relative to the prevailing state-of-the-art.

Tensor factorization methods have recently gained increased popularity. A key feature that renders tensors attractive is the ability to directly model multi-relational data. In this work, we propose ParaSketch, a parallel tensor factorization algorithm that enables massive parallelism, to deal with large tensors. The idea is to compress the large tensor into multiple small tensors, decompose each small tensor in parallel, and combine the results to reconstruct the desired latent factors. Prior art in this direction entails potentially very high complexity in the (Gaussian) compression and final combining stages. Adopting sketching matrices for compression, the proposed method enjoys a dramatic reduction in compression complexity, and features a much lighter combining step. Moreover, theoretical analysis shows that the compressed tensors inherit latent identifiability under mild conditions, hence establishing correctness of the overall approach. Numerical experiments corroborate the theory and demonstrate the effectiveness of the proposed algorithm.

The unprecedented growth in wireless Internet-of-Things and WiFi devices has renewed interest in mechanisms for efficient spectrum reuse. Existing schemes require some level of primary-secondary coordination, cross-channel state estimation and tracking, or activity detection– which complicate implementation. For low-power short-range secondary communication, the main impediment is strong and time-varying (e.g., intermittent) interference from the primary system. This paper proposes a practical underlay scheme that permits reliable secondary communication in this regime. The secondary transmitter merely has to send its signal twice, at very low power - a few dBs above the noise floor, but far below the primary’s interference. Exploiting the repetition structure, reliable and computationally efficient recovery of the secondary signal is possible via canonical correlation analysis (CCA). Experiments using a software radio testbed reveal that, for a secondary user with only two receive antennas, reliable detection of the secondary signal is possible for signal to interference plus noise ratio (SINR) in the range of −20 to −40 dB. The approach works with unknown time-varying channels, digital or analog modulation, it is immune to carrier frequency offset, and, as a side-benefit, it provides means for accurate synchronization of the secondary user even at very low SINR.

Matrix factorization (MF) plays an important role in a wide range of machine learning and data mining models. MF is commonly used to obtain item embeddings and feature representations due to its ability to capture correlations and higher-order statistical dependencies across dimensions. In many applications, the categories of items exhibit a hierarchical tree structure. For instance, human diseases can be divided into coarse categories, e.g., bacterial, and viral. These categories can be further divided into finer categories, e.g., viral infections can be respiratory, gastrointestinal, and exanthematous viral diseases. In e-commerce, products, movies, books, etc., are grouped into hierarchical categories, e.g., clothing items are divided by gender, then by type (formal, casual, etc.). While the tree structure and the categories of the different items may be known in some applications, they have to be learned together with the embeddings in many others. In this work, we propose eTREE, a model that incorporates the (usually ignored) tree structure to enhance the quality of the embeddings. We leverage the special uniqueness properties of Nonnegative MF (NMF) to prove identifiability of eTREE. The proposed model not only exploits the tree structure prior, but also learns the hierarchical clustering in an unsupervised data-driven fashion. We derive an efficient algorithmic solution and a scalable implementation of eTREE that exploits parallel computing, computation caching, and warm start strategies. We showcase the effectiveness of eTREE on real data from various application domains: healthcare, recommender systems, and education. We also demonstrate the meaningfulness of the tree obtained from eTREE by means of domain experts interpretation.

Accurate prediction of the transmission of epidemic diseases such as COVID-19 is crucial for implementing effective mitigation measures. In this work, we develop a tensor method to predict the evolution of epidemic trends for many regions simultaneously. We construct a 3-way spatio-temporal tensor (location, attribute, time) of case counts and propose a nonnegative tensor factorization with latent epidemiological model regularization named STELAR. Unlike standard tensor factorization methods which cannot predict slabs ahead, STELAR enables long-term prediction by incorporating latent temporal regularization through a system of discrete-time difference equations of a widely adopted epidemiological model. We use latent instead of location/attribute-level epidemiological dynamics to capture common epidemic profile sub-types and improve collaborative learning and prediction. We conduct experiments using both county- and state-level COVID-19 data and show that our model can identify interesting latent patterns of the epidemic. Finally, we evaluate the predictive ability of our method and show superior performance compared to the baselines, achieving up to 21% lower root mean square error and 25% lower mean absolute error for county-level prediction.

Collaborative filtering (CF) methods are making an impact on our daily lives in a wide range of applications, including recommender systems and personalization. Latent factor methods, e.g., matrix factorization (MF), have been the state-of-the-art in CF, however they lack interpretability and do not provide a straightforward explanation for their predictions. Explainability is gaining momentum in recommender systems for accountability, and because a good explanation can swing an undecided user. Most recent explainable recommendation methods require auxiliary data such as review text or item content on top of item ratings. In this paper, we address the case where no additional data are available and propose augmenting the classical MF framework for CF with a prior that encodes each user's embedding as a sparse linear combination of item embeddings, and vice versa for each item embedding. Our XPL-CF approach automatically reveals these user-item relationships, which underpin the latent factors and explain how the resulting recommendations are formed. We showcase the effectiveness of XPL-CF on real data from various application domains. We also evaluate the explainability of the user-item relationship obtained from XPL-CF through numeric evaluation and case study examples.

The spectrum underlay concept promises enhanced spectrum utilization without disturbing legacy / licensed or scientific primary users, so long as their interference constraints can be met. Existing underlay schemes assume that both the primary signal to secondary interference plus noise ratio, and the secondary signal to primary interference plus noise ratio can be high enough at the primary and secondary receiver, respectively. Even if the cross-network channel state information is available at the secondary users, these two conflicting requirements are hard to achieve simultaneously in practice. This work proposes a practical data-driven approach that allows a pair of secondary users to reliably communicate in underlay mode while keeping the interference at the primary receiver close to its noise floor. The secondary transmitter merely has to transmit its signal twice, at very low power - above the noise floor, but well below the primary’s interference. It is shown here that reliable detection of the secondary signal is possible via canonical correlation analysis (CCA). Theoretical and experimental results reveal the remarkable detection performance of the proposed CCA-based approach, which does not require any cross-network coordination, or even channel state information.

Real-world spatio-temporal data is often incomplete or inaccurate due to various data loading delays. For example, a location-disease-time tensor of case counts can have multiple delayed updates of recent temporal slices for some locations or diseases. Recovering such missing or noisy (under-reported) elements of the input tensor can be viewed as a generalized tensor completion problem. Existing tensor completion methods usually assume that i) missing elements are randomly distributed and ii) noise for each tensor element is i.i.d. zero-mean. Both assumptions can be violated for spatio-temporal tensor data. We often observe multiple versions of the input tensor with different under-reporting noise levels. The amount of noise can be time- or location-dependent as more updates are progressively introduced to the tensor. We model such dynamic data as a multi-version tensor with an extra tensor mode capturing the data updates. We propose a low-rank tensor model to predict the updates over time. We demonstrate that our method can accurately predict the ground-truth values of many real-world tensors. We obtain up to 27.2% lower root mean-squared-error compared to the best baseline method. Finally, we extend our method to track the tensor data over time, leading to significant computational savings.

Graphs are powerful abstractions that naturally capture the wealth of relationships in our interconnected world. This paper proposes a new approach for graph alignment, a core problem in graph mining. Classical (e.g., spectral) methods use fixed embeddings for both graphs to perform the alignment. In contrast, the proposed approach fixes the embedding of the 'target' graph and jointly optimizes the embedding transformation and the alignment of the 'query' graph. An alternating optimization algorithm is proposed for computing high-quality approximate solutions and compared against the prevailing state-of-the-art graph aligning frameworks using benchmark real-world graphs. The results indicate that the proposed formulation can offer significant gains in terms of matching accuracy and robustness to noise relative to existing solutions for this hard but important problem.

Knowledge graphs (KGs) are powerful tools that codify relational behaviour between entities in knowledge bases. KGs can simultaneously model many different types of subject-predicate-object and higher-order relations. As such, they offer a flexible modeling framework that has been applied to many areas, including biology and pharmacology – most recently, in the fight against COVID-19. The flexibility of KG modeling is both a blessing and a challenge from the learning point of view. In this paper we propose a novel coupled tensor-matrix framework for KG embedding. We leverage tensor factorization tools to learn concise representations of entities and relations in knowledge bases and employ these representations to perform drug repurposing for COVID-19. Our proposed framework is principled, elegant, and achieves 100% improvement over the best baseline in the COVID-19 drug repurposing task using a recently developed biological KG.

Given an undirected graph, the Densest-k-Subgraph problem (DkS) seeks to find a subset of k vertices such that the sum of the edge weights in the corresponding subgraph is maximized. The problem is known to be NP-hard, and is also very difficult to approximate, in the worst-case. In this paper, we present a new convex relaxation for the problem. Our key idea is to reformulate DkS as minimizing a submodular function subject to a cardinality constraint. Exploiting the fact that submodular functions possess a convex, continuous extension (known as the Lovasz extension), we propose to minimize the Lovasz extension over the convex hull of the cardinality constraints. Although the Lovasz extension of a submodular function does not admit an analytical form in general, for DkS we show that it does. We leverage this result to develop a highly scalable algorithm based on the Alternating Direction Method of Multipliers (ADMM) for solving the relaxed problem. Coupled with a pair of fortuitously simple rounding schemes, we demonstrate that our approach outperforms existing baselines on real-world graphs and can yield high quality sub-optimal solutions which typically are a posteriori no worse than65-80%of the optimal density.

Joint analysis of data from multiple information repositories facilitates uncovering the underlying structure in heterogeneous datasets. Single and coupled matrix-tensor factorization (CMTF) has been widely used in this context for imputation-based recommendation from ratings, social network, and other user-item data. When this side information is in the form of item-item correlation matrices or graphs, existing CMTF algorithms may fall short. Alleviating current limitations, we introduce a novel model coined coupled graph-tensor factorization (CGTF) that judiciously accounts for graph-related side information. The CGTF model has the potential to overcome practical challenges, such as missing slabs from the tensor and/or missing rows/columns from the correlation matrices. A novel alternating direction method of multipliers (ADMM) is also developed that recovers the nonnegative factors of CGTF. Our algorithm enjoys closed-form updates that result in reduced computational complexity and allow for convergence claims. A novel direction is further explored by employing the interpretable factors to detect graph communities having the tensor as side information. The resulting community detection approach is successful even when some links in the graphs are missing. Results with real data sets corroborate the merits of the proposed methods relative to state-of-the-art competing factorization techniques in providing recommendations and detecting communities.

Function approximation from input and output data pairs constitutes a fundamental problem in supervised learning. Deep neural networks are currently the most popular method for learning to mimic the input-output relationship of a general nonlinear system, as they have proven to be very effective in approximating complex highly nonlinear functions. In this work, we show that identifying a general nonlinear function y = ƒ(x1,…,xN) from input-output examples can be formulated as a tensor completion problem and under certain conditions provably correct nonlinear system identification is possible. Specifically, we model the interactions between the N input variables and the scalar output of a system by a single N-way tensor, and setup a weighted low-rank tensor completion problem with smoothness regularization which we tackle using a block coordinate descent algorithm. We extend our method to the multi-output setting and the case of partially observed data, which cannot be readily handled by neural networks. Finally, we demonstrate the effectiveness of the approach using several regression tasks including some standard benchmarks and a challenging student grade prediction task.

Graph matching aims to align a pair of graphs by minimizing their edge disagreements. As the problem is NP–hard in the worst-case, various methods have been proposed for approximately solving the problem. One popular approach is to relax the combinatorial problem to a continuous formulation, whose solution represents a soft correspondence between the vertex-sets of the graphs. Previous work has primarily motivated such soft matching formulations as an intermediate step towards obtaining hard correspondences. In this paper, we depart from this viewpoint and provide an alternate motivation for soft matching as a means of identifying classes of topologically-invariant subgraphs, which cannot be revealed by hard correspondences. Drawing on this observation, we consider the family of doubly-stochastic relaxations for graph matching and propose a new convex relaxation for the problem. We establish that the objective function of our formulation can be interpreted as the tightest convex relaxation of the combinatorial quadratic graph matching objective function in a certain sense, and describe an efficient first-order algorithm for computing its solution. Through experiments conducted on real-world data, we demonstrate the empirical effectiveness of the algorithm relative to the prevailing relaxations for graph matching.

Mining dense subgraphs is an important primitive across a spectrum of graph-mining tasks. In this work, we formally establish that two recurring characteristics of real-world graphs, namely heavy-tailed degree distributions and large clustering coefficients, imply the existence of substantially large vertex neighborhoods with high edge-density. This observation suggests a very simple approach for extracting large quasi-cliques: simply scan the vertex neighborhoods, compute the clustering coefficient of each vertex, and output the best such subgraph. The implementation of such a method requires counting the triangles in a graph, which is a well-studied problem in graph mining. When empirically tested across a number of real-world graphs, this approach reveals a surprise: vertex neighborhoods include maximal cliques of non-trivial sizes, and the density of the best neighborhood often compares favorably to subgraphs produced by dedicated algorithms for maximizing subgraph density. For graphs with small clustering coefficients, we demonstrate that small vertex neighborhoods can be refined using a local-search method to grow larger cliques and near-cliques. Our results indicate that contrary to worst-case theoretical results, mining cliques and quasi-cliques of non-trivial sizes from real-world graphs is often not a difficult problem, and provides motivation for further work geared towards a better explanation of these empirical successes.

Seeking outside funding is a critical task for many companies, but it is also challenging to identify the potential investors given the heterogeneity in size, interests, and expertise. In this work, we propose to tackle this problem via data-driven approaches. Towards this end, we first harvest relevant publicly available data about institutional investors and their holdings in publicly traded companies, as well as key financial metrics on the same set of public companies. Using these data, we approach the problem of interest as a recommender system with side information. We formulate two principal goals: predicting “missing” (potential) investor holding positions; and providing top-K investor recommendations. For each goal, custom recommendation algorithms are proposed to achieve the corresponding objective. Numerical experiments are carefully designed to validate the effectiveness of the proposed algorithms, which exhibit good performance in practice.

Providing reliable service to users close to the edge between cells remains a challenge in cellular systems, even as 5G deployment is around the corner. These users are subject to significant signal attenuation, which also degrades their uplink channel estimates. Even joint detection using base station (BS) cooperation often fails to reliably detect such users, due to near-far power imbalance, and channel estimation errors. Is it possible to bypass the channel estimation stage and design a detector that can reliably detect cell-edge user signals under significant near-far imbalance? This paper shows, perhaps surprisingly, that the answer is affirmative - albeit not via traditional multiuser detection. Exploiting that cell-edge user signals are weak but common to different base stations, while cell-center users are unique to their serving BS, this paper establishes an elegant connection between cell-edge user detection and canonical correlation analysis (CCA) of the associated space-time baseband-equivalent matrices. It proves that CCA identifies the common subspace of these matrices, even under significant intra-and inter-cell interference. The resulting mixture of cell-edge user signals can subsequently be unraveled using a well-known algebraic signal processing technique. Interestingly, the proposed approach does not even require that the signals from the different base stations are synchronized - the right synchronization can be automatically determined as well. Experimental results demonstrate that the proposed approach achieves order of magnitude BER improvements compared to `oracle' multiuser detection that assumes perfect knowledge of the cell-center user channels.

We study the problem of learning a mixture model of non-parametric product distributions. The problem of learning a mixture model is that of finding the component distributions along with the mixing weights using observed samples generated from the mixture. The problem is well-studied in the parametric setting, i.e., when the component distributions are members of a parametric family - such as Gaussian distributions. In this work, we focus on multivariate mixtures of non-parametric product distributions and propose a two-stage approach which recovers the component distributions of the mixture under a smoothness condition. Our approach builds upon the identifiability properties of the canonical polyadic (low-rank) decomposition of tensors, in tandem with Fourier and Shannon-Nyquist sampling staples from signal processing. We demonstrate the effectiveness of the approach on synthetic and real datasets.

Predicting the response of cancer cells to drugs is an important problem in pharmacogenomics. Recent efforts in generation of large scale datasets profiling gene expression and drug sensitivity in cell lines have provided a unique opportunity to study this problem. However, one major challenge is the small number of samples (cell lines) compared to the number of features (genes) even in these large datasets. We propose a collaborative filtering like algorithm for modeling gene-drug relationship to identify patients most likely to benefit from a treatment. Due to the correlation of gene expressions in different cell lines, the gene expression matrix is approximately low-rank, which suggests that drug responses could be estimated from a reduced dimension latent space of the gene expression. Towards this end, we propose a joint low-rank matrix factorization and latent linear regression approach. Experiments with data from the Genomics of Drug Sensitivity in Cancer database are included to show that the proposed method can predict drug-gene associations better than the state-of-the-art methods.

Sampling lies at the heart of signal processing. The celebrated Shan-non - Nyquist theorem states that in order to reconstruct a continuous or discrete time signal from uniform samples one must sample at a rate twice the highest frequency present in the signal. Numerous signals and images of interest, however, are not even approximately bandlimited. While much progress has happened in recent years, reconstruction from sub-Nyquist samples still hinges on the use of random / incoherent (aggregate) sampling patterns, instead of uniform or regular sampling, which is far more simple, practical, and natural in many applications. In this work, we study regular sampling and reconstruction of three- or higher-dimensional signals (tensors). We prove that exact tensor reconstruction from regular samples is feasible under mild conditions on the rank of the tensor. Furthermore we cast the functional magnetic resonance imaging (fMRI) acceleration task as a regular tensor sampling problem and provide an algorithmic framework that effectively handles the reconstruction task. Experiments based on synthetic data and real fMRI data showcase the effectiveness of our approach.

We consider the NP-hard combinatorial optimization problem of minimizing arbitrary quadratic forms over the {0, 1 } (Boolean) lattice. While polynomial-time approximation algorithms do exist for such problems, they suffer from the practical drawback of being computationally involved - often a side effect of being agnostic to the combinatorial structure inherent in the problem. In this paper, we propose a computationally lightweight approximation alternative which specifically exploits the combinatorial structure of the problem. The key result underlying our approach is that any Boolean quadratic function can be expressed as a difference of quadratic sub-modular functions, which enables us to construct and iteratively minimize a sequence of global submodular upper bounds on the cost function. This entails solving a quadratic submodular function minimization problem at each step, which can be efficiently accomplished via the seminal Max-Flow algorithm. Overall, our algorithm performs iterative approximation by solving a sequence of maximum-flow problems. The merits of using this approach are illustrated via simulations which indicate the very favorable performance of our algorithm.

The Canonical Polyadic Decomposition (CPD) is one of the most basic tensor models used in signal processing and machine learning. Despite its wide applicability, identifiability conditions and algorithms for CPD in cases where the tensor is incomplete are lagging behind its practical use. We first present a tensor-based framework for bilinear factorizations subject to monomial constraints, called monomial factorizations. Next, we explain that the CPD of a tensor that has missing fibers can be interpreted as a monomial factorization problem. Finally, using the monomial factorization interpretation, we show that CPD recovery conditions can be obtained that only rely on the observed fibers of the tensor.

Graph matching, the problem of aligning a pair of graphs so as to minimize their edge disagreements, has received widespread attention owing to its broad spectrum of applications in data science. As the problem is NP-hard in the worst-case, a variety of approximation algorithms have been proposed for obtaining high quality, suboptimal solutions. In this paper, we approach the task of designing an efficient polynomial-time approximation algorithm for graph matching from a previously unconsidered perspective. Our key result is that graph matching can be formulated as maximizing a monotone, supermodular set function subject to matroid intersection constraints. We leverage this fact to apply a discrete optimization variant of the minorization-maximization algorithm which exploits supermodularity of the objective function to iteratively construct and maximize a sequence of global lower bounds on the objective. At each step, we solve a maximum weight matching problem in a bipartite graph. Differing from prior approaches, the algorithm exploits the combinatorial structure inherent in the problem to generate a sequence of iterates featuring monotonically non-decreasing objective value while always adhering to the combinatorial matching constraints. Experiments on real-world data demonstrate the empirical effectiveness of the algorithm relative to the prevailing state-of-the-art.

Machine learning and data driven approaches have recently received much attention as a key enabler for future 5G and beyond wireless networks. Yet, the evolution towards learning-based data driven networks is still in its infancy, and much of the realization of the promised benefits requires thorough research and development. Fundamental questions remain as to where and how ML can really complement the well-established, well-tested communication systems designed over the last four decades. Moreover, adaptation of machine learning methods is likely needed to realize their full potential in the wireless context. This is particularly challenging for the lower layers of the protocol stack, where the constraints, problem formulation, and even the objectives may fundamentally differ from the typical scenarios to which machine learning has been successfully applied in recent years. In addition, a thorough understanding of the fundamental performance limits is also essential in order to establish quality-of-service guarantees that are common in communication system design. Such challenges, which lie at the core of the special issue, can be categorized into a number of research topics ranging from the optization of neural networks architectures that are suited to wireless communication links (inclusing autoencoders, generative adversarial networks, reinforcement based networks etc) to performance analysis, to the acceleration of data-driven training, and possibly in distributed settings. The application domains within the wireless realm are also quite diverse in nature with promising preliminary results in the area of physical layer design and resource allocation as well as for network service orchestrations. Testbeds and experimental evaluations are also begining to be reported.

Machine learning and data driven approaches have recently received much attention as a key enabler for future 5G and beyond wireless networks. Yet, the evolution towards learning-based data driven networks is still in its infancy, and much of the realization of the promised benefits requires thorough research and development. Fundamental questions remain as to where and how ML can really complement the well-established, well-tested communication systems designed over the last four decades. Moreover, adaptation of machine learning methods is likely needed to realize their full potential in the wireless context. This is particularly challenging for the lower layers of the protocol stack, where the constraints, problem formulation, and even the objectives may fundamentally differ from the typical scenarios to which machine learning has been successfully applied in recent years. In addition, a thorough understanding of the fundamental performance limits is also essential in order to establish quality-of-service guarantees that are common in communication system design. Such challenges, which lie at the core of the special issue, can be categorized into a number of research topics ranging from the optization of neural networks architectures that are suited to wireless communication links (inclusing autoencoders, generative adversarial networks, reinforcement based networks etc) to performance analysis, to the acceleration of data-driven training, and possibly in distributed settings. The application domains within the wireless realm are also quite diverse in nature with promising preliminary results in the area of physical layer design and resource allocation as well as for network service orchestrations. Testbeds and experimental evaluations are also begining to be reported.

Thanks to the recent advances in processing speed, data acquisition and storage, machine learning (ML) is penetrating every facet of our lives, and transforming research in many areas in a fundamental manner. Wireless communications is another success story - ubiquitous in our lives, from handheld devices to wearables, smart homes, and automobiles. While recent years have seen a flurry of research activity in exploiting ML tools for various wireless communication problems, the impact of these techniques in practical communication systems and standards is yet to be seen. In this paper, we review some of the major promises and challenges of ML in wireless communication systems, focusing mainly on the physical layer. We present some of the most striking recent accomplishments that ML techniques have achieved with respect to classical approaches, and point to promising research directions where ML is likely to make the biggest impact in the near future. We also highlight the complementary problem of designing physical layer techniques to enable distributed ML at the wireless network edge, which further emphasizes the need to understand and connect ML with fundamental concepts in wireless communications.

In topic modeling, identifiability of the topics is an essential issue. Many topic modeling approaches have been developed under the premise that each topic has a characteristic anchor word that only appears in that topic. The anchor-word assumption is fragile in practice, because words and terms have multiple uses; yet it is commonly adopted because it enables identifiability guarantees. Remedies in the literature include using three- or higher-order word co-occurence statistics to come up with tensor factorization models, but such statistics need many more samples to obtain reliable estimates, and identifiability still hinges on additional assumptions, such as consecutive words being persistently drawn from the same topic. In this work, we propose a new topic identification criterion using second order statistics of the words. The criterion is theoretically guaranteed to identify the underlying topics even when the anchor-word assumption is grossly violated. An algorithm based on alternating optimization, and an efficient primal-dual algorithm are proposed to handle the resulting identification problem. The former exhibits high performance and is completely parameter-free; the latter affords up to 200 times speedup relative to the former, but requires step-size tuning and a slight sacrifice in accuracy. A variety of real text copora are employed to showcase the effectiveness of the approach, where the proposed anchor-free method demonstrates substantial improvements compared to a number of anchor-word based approaches under various evaluation metrics.

This letter revisits the channel estimation problem for MIMO systems with one-bit analog-to-digital converters (ADCs) through a novel algorithm-Amplitude Retrieval (AR). Unlike the state-of-the-art methods such as those based on one-bit compressive sensing, AR takes a different approach. It accounts for the lost amplitudes of the one-bit quantized measurements, and performs channel estimation and amplitude completion jointly. This way, the direction information of the propagation paths can be estimated via accurate direction finding algorithms in array processing, e.g., maximum likelihood. The upsot is that AR is able to handle off-grid angles and provide more accurate channel estimates. Simulation results are included to showcase the advantages of AR.

Generalized canonical correlation analysis (GCCA) integrates information from data samples that are acquired at multiple feature spaces (or `views') to produce low-dimensional representations-which is an extension of classical two-view CCA. Since the 1960s, (G)CCA has attracted much attention in statistics, machine learning, and data mining because of its importance in data analytics. Despite these efforts, the existing GCCA algorithms have serious complexity issues. The memory and computational complexities of the existing algorithms usually grow as a quadratic and cubic function of the problem dimension (the number of samples / features), respectively-e.g., handling views with ≈1,000 features using such algorithms already occupies ≈106memory and the periteration complexity is ≈109flops-which makes it hard to push these methods much further. To circumvent such difficulties, we first propose a GCCA algorithm whose memory and computational costs scale linearly in the problem dimension and the number of nonzero data elements, respectively. Consequently, the proposed algorithm can easily handle very large sparse views whose sample and feature dimensions both exceed 100,000. Our second contribution lies in proposing two distributed algorithms for GCCA, which compute the canonical components of different views in parallel and thus can further reduce the runtime significantly if multiple computing agents are available. We provide detailed convergence analyses of the proposed algorithms and show that all the largescale GCCA algorithms converge to a Karush-Kuhn-Tucker (KKT) point at least sublinearly. Judiciously designed synthetic and realdata experiments are employed to showcase the effectiveness of the proposed algorithms.

Epanechnikov Mean Shift is a simple yet empirically very effective algorithm for clustering. It localizes the centroids of data clusters via estimating modes of the probability distribution that generates the data points, using the "optimal" Epanechnikov kernel density estimator. However, since the procedure involves non-smooth kernel density functions,the convergence behavior of Epanechnikov mean shift lacks theoretical support as of this writing---most of the existing analyses are based on smooth functions and thus cannot be applied to Epanechnikov Mean Shift. In this work, we first show that the original Epanechnikov Mean Shift may indeed terminate at a non-critical point, due to the non-smoothness nature. Based on our analysis, we propose a simple remedy to fix it. The modified Epanechnikov Mean Shift is guaranteed to terminate at a local maximum of the estimated density, which corresponds to a cluster centroid, within a inite number of iterations. We also propose a way to avoid running the Mean Shift iterates from every data point, while maintaining good clustering accuracies under non-overlapping spherical Gaussian mixture models. This further pushes Epanechnikov Mean Shift to handle very large and high-dimensional data sets. Experiments show surprisingly good performance compared to the Lloyd's K-means algorithm and the EM algorithm.

The 3GPP suggests to combine dual polarized (DP) antenna arrays with the double directional (DD) channel model for downlink channel estimation. This combination strikes a good balance between high-capacity communications and parsimonious channel modeling, and also brings limited feedback schemes for downlink channel estimation within reach. However, most existing channel estimation work under the DD model has not considered DP arrays, perhaps because of the complex array manifold and the resulting difficulty in algorithm design. In this paper, we first reveal that the DD channel with DP arrays at the transmitter and receiver can be naturally modeled as a low-rank four-way tensor, and thus the parameters can be effectively estimated via tensor decomposition algorithms. To reduce computational complexity, we show that the problem can be recast as a four-snapshot three-dimensional harmonic retrieval problem, which can be solved using computationally efficient subspace methods. On the theory side, we show that the DD channel with DP arrays is identifiable under very mild conditions, leveraging identifiability of low-rank tensors. Numerical simulations are employed to showcase the effectiveness of our methods.

Energy disaggregation is the task of decomposing the aggregated power consumption readings of a household into its constituent parts. In this paper, we propose a supervised, non-parametric framework for energy disaggregation. We demonstrate that the problem is equivalent to maximizing a set-function subject to combinatorial constraints, which is NP-hard in its general form. A simple polynomial-time successive approximation algorithm which exploits submodularity per set-block to iteratively maximize a sequence of global lower bounds of the objective function is proposed for obtaining approximate solutions. Experiments on real data indicate the superior disaggregation performance and scalability of our approach over a state-of-the-art parametric Factorial Hidden Markov Model based framework employing convex relaxation.

The sum-of-correlations (SUMCOR) generalized canonical correlation analysis (GCCA) aims at producing low-dimensional representations of multiview data via enforcing pairwise similarity of the reduced-dimension views. SUMCOR has been applied to a large variety of applications including blind separation, multilingual word embedding, and cross-modality retrieval. Despite the NP-hardness of SUMCOR, recent work has proposed effective algorithms for handling it at very large scale. However, the existing scalable algorithms are not easy to extend to incorporate structural regularization and prior information - which are critical for real-world applications where outliers and modeling mismatches are present. In this work, we propose a new computational framework for large-scale SUMCOR GCCA. The algorithm can easily incorporate a suite of structural regularizers which are frequently used in data analytics, has lightweight updates and low memory complexity, and can be easily implemented in a parallel fashion. The proposed algorithm is also guaranteed to converge to a Karush-Kuhn-Tucker (KKT) point of the regularized SUMCOR problem. Carefully designed simulations are employed to demonstrate the effectiveness of the proposed algorithm.

This work focuses on the problem of fusing a hyperspectral image (HSI) and a multispectral image (MSI) to produce a super-resolution image that admits high spatial and spectral resolutions. Existing algorithms are mostly based on joint low-rank factorization of the ma-tricized HSI and MSI. This framework is effective to some extent, but several challenges remain. First, it is unclear whether or not the super-resolution image is identifiable in theory under this framework, while identifiability usually plays an essential role in such estimation problems. Second, most algorithms assume that the degradation operators from the super-resolution image to the HSI and MSI are known or can be easily estimated - which is hardly true in practice. In this work, we propose a novel coupled tensor decomposition method that can effectively circumvent these issues. The proposed approach guarantees the identifiability of the super-resolution image under realistic conditions. The method can work even without knowing the spatial degradation operator, which could be hard to accurately estimate in practice. Simulations using AVIRIS Cuprite data are employed to demonstrate the effectiveness of the proposed approach.

Quadratically constrained quadratic programming (QCQP) forms an important class of optimization tasks in various engineering disciplines. Fast identification of a feasible point under low computational complexity load is critical for several approximation techniques which have been developed to solve non-convex QCQPs. This paper introduces two projection-based techniques to compute feasible points of non-convex QCQPs with low computational complexity footprints: The first one employs successive projection mappings, while the second one builds on a composition of successive and averaged projection steps. Extensive experiments on synthetically generated instances of non-convex quadratically constrained feasibility problems demonstrate that the simple successive-projection based technique compares favorably against state-of-the-art feasible point pursuit methods which capitalize on successive convex approximation, parallel projections and computationally demanding interior-point techniques.

We address the challenge of reconstructing historical counts from aggregated, possibly overlapping historical reports. For example, given the monthly and weekly sums, how can we find the daily counts of people infected with flu? We propose an approach, called ARES (Automatic REStoration), that performs automatic data reconstruction in two phases: (1) first, it estimates the sequence of historical counts utilizing domain knowledge, such as smoothness and periodicity of historical events; (2) then, it uses the estimated sequence to learn notable patterns in the target sequence to refine the reconstructed time series. In order to derive such patterns, ARES uses an annihilating filter technique. The idea is to learn a linear shift-invariant operator whose response to the desired sequence is (approximately) zero-yielding a set of null-space equations that the desired signal should satisfy, without the need for the accompanying data. The reconstruction accuracy can be further improved by applying the second phase iteratively. We evaluate ARES on the real epidemiological data from the Tycho project and demonstrate that ARES recovers historical data from aggregated reports with high accuracy. In particular, it considerably outperforms top competitors, including least squares approximation and the more advanced H-FUSE method (42% and 34% improvement based on average RMSE, respectively).

Hyperspectral super-resolution refers to the task of fusing a hyperspectral image (HSI) and a multispectral image (MSI) in order to produce a super-resolution image (SRI) that has high spatial and spectral resolution. Popular methods leverage matrix factorization that models each spectral pixel as a convex combination of spectral signatures belonging to a few endmembers. These methods are considered state-of-the-art, but several challenges remain. First, multiband images are naturally three dimensional (3-d) signals, while matrix methods usually ignore the 3-d structure, which is prone to information losses. Second, these methods do not provide identifiability guarantees under which the reconstruction task is feasible. Third, a tacit assumption is that the degradation operators from SRI to MSI and HSI are known - which is hardly the case in practice. Recently [1], [2] proposed a coupled tensor factorization approach to handle these issues. In this work we propose a hybrid model that combines the benefits of tensor and matrix factorization approaches. We also develop a new algorithm that is mathematically simple, enjoys identifiability under relaxed conditions and is completely agnostic of the spatial degradation operator. Experimental results with real hyperspectral data showcase the effectiveness of the proposed approach.

We present a new algorithm for identifying the transition and emission probabilities of a hidden Markov model (HMM) from the emitted data. Expectation-maximization becomes computationally prohibitive for long observation records, which are often required for identification. The new algorithm is particularly suitable for cases where the available sample size is large enough to accurately estimate second-order output probabilities, but not higher-order ones. We show that if one is only able to obtain a reliable estimate of the pairwise co-occurrence probabilities of the emissions, it is still possible to uniquely identify the HMM if the emission probability is sufficiently scattered. We apply our method to hidden topic Markov modeling, and demonstrate that we can learn topics with higher quality if documents are modeled as observations of HMMs sharing the same emission (topic) probability, compared to the simple but widely used bag-of-words model.

Sparse tensor factorization is a popular tool in multi-way data analysis and is used in applications such as cybersecurity, recommender systems, and social network analysis. In many of these applications, the tensor is not known a priori and instead arrives in a streaming fashion for a potentially unbounded amount of time. Existing approaches for streaming sparse tensors are not practical for unbounded streaming because they rely on maintaining the full factorization of the data, which grows linearly with time. In this work, we present CP-stream, an algorithm for streaming factorization in the model of the canonical polyadic decomposition which does not grow linearly in time or space, and is thus practical for long-term streaming. Additionally, CP-stream incorporates user-specified constraints such as non-negativity which aid in the stability and interpretability of the factorization. An evaluation of CP-stream demonstrates that it converges faster than state-of-the-art streaming algorithms while achieving lower reconstruction error by an order of magnitude. We also evaluate it on real-world sparse datasets and demonstrate its usability in both network traffic analysis and discussion tracking. Our evaluation uses exclusively public datasets and our source code is released to the public as part of SPLATT, an open source high-performance tensor factorization toolkit.

Tensor factorization methods have gained increased popularity in the data mining community. A key feature that renders tensors attractive is the essential uniqueness (identifiability) of their decomposition into latent factors: this is crucial for explanatory data analysis – model uniqueness makes interpretations well grounded. In this work, we propose ParaSketch, a distributed tensor factorization algorithm that enables massive parallelism, to deal with large tensors. The idea is to compress/sketch the large tensor into multiple small tensors, decompose each small tensor, and combine the results to reconstruct the desired latent factors. Prior art in this direction entails potentially very high complexity in the (Gaussian) compression and final combining stages. Utilizing sketching matrices for compression, the proposed method greatly reduces compression complexity, and features much simpler combining. Moreover, theoretical analysis shows that the compressed tensors inherit latent identifiability under mild conditions, hence establishing correctness of the overall approach. Our approach to establish identifiability for the sketched tensor is original, and of interest in its own right.

Recovering a time sequence of events from multiple aggregated and possibly overlapping reports is a major challenge in historical data fusion. The goal is to reconstruct a higher resolution event sequence from a mixture of lower resolution samples as accurately as possible. For example, we may aim to disaggregate overlapping monthly counts of people infected with measles into weekly counts. In this paper, we propose a novel data disaggregation method, called H ome R un , that exploits an alternative representation of the sequence and finds the spectrum of the target sequence. More specifically, we formulate the problem as so-called basis pursuit using the Discrete Cosine Transform (DCT) as a sparsifying dictionary and impose non-negativity and smoothness constraints. H ome R un utilizes the energy compaction feature of the DCT by finding the sparsest spectral representation of the target sequence that contains the largest (most important) coefficients. We leverage the Alternating Direction Method of Multipliers to solve the resulting optimization problem with scalable and memory efficient steps. Experiments using real epidemiological data show that our method considerably outperforms the state-of-the-art techniques, especially when the DCT of the sequence has a high degree of energy compaction.

In this letter, we propose a new identification criterion that guarantees the recovery of the low-rank latent factors in the nonnegative matrix factorization (NMF) generative model, under mild conditions. Specifically, using the proposed criterion, it suffices to identify the latent factors if the rows of one factor are sufficiently scattered over the nonnegative orthant, while no structural assumption is imposed on the other factor except being full-rank. This is by far the mildest condition under which the latent factors are provably identifiable from the NMF model.

Unlike dimensionality reduction (DR) tools for single-view data, e.g., principal component analysis (PCA), canonical correlation analysis (CCA) and generalized CCA (GCCA) are able to integrate information from multiple feature spaces of data. This is critical in multi-modal data fusion and analytics, where samples from a single view may not be enough for meaningful DR. In this work, we focus on a popular formulation of GCCA, namely, MAX-VAR GCCA. The classic MAX-VAR problem is optimally solvable via eigen-decomposition, but this solution has serious scalability issues. In addition, how to impose regularizers on the sought canonical components was unclear - while structure-promoting regularizers are often desired in practice. We propose an algorithm that can easily handle datasets whose sample and feature dimensions are both large by exploiting data sparsity. The algorithm is also flexible in incorporating regularizers on the canonical components. Convergence properties of the proposed algorithm are carefully analyzed. Numerical experiments are presented to showcase its effectiveness.

Quadratically Constrained Quadratic Programming (QCQP) is NP-hard in its general non-convex form, but it frequently arises in engineering design and applications ranging from state estimation to beamforming and clustering. Several polynomial-time approximation algorithms exist for non-convex QCQP problems (QCQPs), but their success hinges upon the ability to find at least one feasible point - which is also hard for a general problem instance. In this paper, we present a framework for computing feasible points of general non-convex QCQPs using simple first-order methods. Our approach features low computational and memory requirements, which makes it well-suited for application on large-scale problems. Experiments indicate the empirical effectiveness of our approach, despite currently lacking theoretical guarantees.

We consider the problem of nonnegative tensor factorization. Our aim is to derive an efficient algorithm that is also suitable for parallel implementation. We adopt the alternating optimization (AO) framework and solve each matrix nonnegative least-squares problem via a Nesterov-type algorithm for strongly convex problems. We describe a parallel implementation of the algorithm and measure the speedup attained by itsMessage Passing Interface implementation on a parallel computing environment. It turns out that the attained speedup is significant, rendering our algorithm a competitive candidate for the solution of very large-scale dense nonnegative tensor factorization problems.

Owing to the rapidly increasing traffic demands on satellite connectivity, the current exclusive frequency allocation is becoming obsolete. Instead, aggressive frequency reuse and interference mitigation techniques are promising ideas that both industry and academia are investigating. This paper proposes an optimization precoding technique for dealing with the multibeam interference due to the aggressive frequency reuse. In contrast to general multiuser multiple input multiple output (MIMO) schemes, multibeam satellite precoding techniques call for frame-by-frame quadratically constrained quadratic optimization of a large number of variables. We focus on the multigroup multicast beamforming optimization problem, and we propose to adopt a consensus-based alternating direction method of multipliers (C-ADMM) approach, in order to mitigate complexity. The proposed C-ADMM approach is shown to exhibit comparable optimization performance at considerably lower complexity relative to the prior state-of-art for the formulation considered.

Most learning approaches treat dimensionality reduction (DR) and clustering separately (i.e., sequentially), but recent research has shown that optimizing the two tasks jointly can substantially improve the performance of both. The premise behind the latter genre is that the data samples are obtained via linear transformation of latent representations that are easy to cluster; but in practice, the transformation from the latent space to the data can be more complicated. In this work, we assume that this transformation is an unknown and possibly nonlinear function. To recover the `clustering-friendly’ latent representations and to better cluster the data, we propose a joint DR and K-means clustering approach in which DR is accomplished via learning a deep neural network (DNN). The motivation is to keep the advantages of jointly optimizing the two tasks, while exploiting the deep neural network’s ability to approximate any nonlinear function. This way, the proposed approach can work well for a broad class of generative models. Towards this end, we carefully design the DNN structure and the associated joint optimization criterion, and propose an effective and scalable algorithm to handle the formulated optimization problem. Experiments using different real datasets are employed to showcase the effectiveness of the proposed approach.

How close can we zoom in to observe brain activity? Our understanding is limited by the resolution of imaging modalities that exhibit good spatial but poor temporal resolution, or vice-versa. In this paper, we propose BrainZoom, an efficient imaging algorithm that cross-leverages multi-modal brain signals. BrainZoom (a) constructs high resolution brain images from multi-modal signals, (b) is scalable, and (c) is flexible in that it can easily incorporate various priors on the brain activities, such as sparsity, low rank, or smoothness. We carefully formulate the problem to tackle nonlinearity in the measurements (via variable splitting) and auto-scale between different modal signals, and judiciously design an inexact alternating optimization-based algorithmic framework to handle the problem with provable convergence guarantees. Our experiments using a popular realistic brain signal simulator to generate fMRI and MEG demonstrate that high spatio-temporal resolution brain imaging is possible from these two modalities. The experiments also suggest that smoothness seems to be the best prior, among several we tried.

In this paper, we address the challenge of recovering a time sequence of counts from aggregated historical data. For example, given a mixture of the monthly and weekly sums, how can we find the daily counts of people infected with flu? In general, what is the best way to recover historical counts from aggregated, possibly overlapping historical reports, in the presence of missing values? Equally importantly, how much should we trust this reconstruction? We propose H-Fuse, a novel method that solves above problems by allowing injection of domain knowledge in a principled way, and turning the task into a well-defined optimization problem. H-Fuse has the following desirable properties: (a) Effectiveness, recovering historical data from aggregated reports with high accuracy; (b) Self-awareness, providing an assessment of when the recovery is not reliable; (c) Scalability, computationally linear on the size of the input data. Experiments on the real data (epidemiology counts from the Tycho project [13]) demonstrates that H-FUSE reconstructs the original data 30 – 81% better than the least squares method.

This work proposes a new limited feedback channel estimation framework. The proposed approach exploits a sparse representation of the double directional wireless channel model involving an over complete dictionary that accounts for the antenna directivity patterns at both base station (BS) and user equipment (UE). Under this sparse representation, a computationally efficient limited feedback algorithm that is based on single-bit compressive sensing is proposed to effectively estimate the downlink channel. The algorithm is lightweight in terms of computation, and suitable for real-time implementation in practical systems. More importantly, under our design, using a small number of feedback bits, very satisfactory channel estimation accuracy is achieved even when the number of BS antennas is very large, which makes the proposed scheme ideal for massive MIMO 5G cellular networks. Judiciously designed simulations reveal that the proposed algorithm outperforms a number of popular feedback schemes in terms of beam forming gain for subsequent downlink transmission, and reduces feedback overhead substantially when the BS has a large number of antennas.

Tensors and tensor decompositions are very powerful and versatile tools that can model a wide variety of heterogeneous, multiaspect data. As a result, tensor decompositions, which extract useful latent information out of multiaspect data tensors, have witnessed increasing popularity and adoption by the data mining community. In this survey, we present some of the most widely used tensor decompositions, providing the key insights behind them, and summarizing them from a practitioner’s point of view. We then provide an overview of a very broad spectrum of applications where tensors have been instrumental in achieving state-of-the-art performance, ranging from social network analysis to brain data analysis, and from web mining to healthcare. Subsequently, we present recent algorithmic advances in scaling tensor decompositions up to today’s big data, outlining the existing systems and summarizing the key ideas behind them. Finally, we conclude with a list of challenges and open problems that outline exciting future research directions.

This paper focuses on volume minimization (VolMin)-based structured matrix factorization (SMF), which factors a data matrix into a full-column rank basis and a coefficient matrix whose columns reside in the unit simplex. The VolMin criterion achieves this goal via finding a minimum-volume enclosing convex hull of the data. Recent works showed that VolMin guarantees the identifiability of the factor matrices under mild and realistic conditions, which suit many applications in signal processing and machine learning. However, the existing VolMin algorithms are sensitive to outliers or lack efficiency in dealing with volume-associated cost functions. In this work, we propose a new VolMin-based matrix factorization criterion and algorithm that take outliers into consideration. The proposed algorithm detects outliers and suppress them automatically, and it does so in an algorithmically very simple way. Simulations are used to showcase the effectiveness of the proposed algorithm.

This paper considers phase retrieval from the magnitude of 1-D oversampled Fourier measurements. We first revisit the well-known lack of identifiability in this case, and point out that there always exists a solution that is minimum phase, even though the desired signal is not. Next, we explain how the least-squares formulation of this problem can be optimally solved via PhaseLift followed by spectral factorization, and this solution is always minimum phase. A simple approach is then proposed to circumvent non-identifiability: adding an impulse to an arbitrary complex signal (offset to the Fourier transform) before taking the quadratic measurements, so that a minimum phase signal is constructed and thus can be uniquely estimated. Simulations with synthetic data show the effectiveness of the proposed method.

Estimating the power spectrum of a wide-sense stationary stochastic process is a core component of several signal processing tasks. Distributed spectrum sensing problems naturally emerge in cases where measurements of different realizations of a stochastic process are collected at multiple spatial locations. This paper describes a distributed power spectrum sensing scheme for stochastic processes which are well represented by an autoregressive (AR) process. The sensing model comprises a network of scattered low-end sensors which transmit randomly filtered, one bit quantized power measurements to a fusion center. The problem of AR power spectrum estimation from such binary power measurements is cast as a non-convex optimization problem, and an alternating minimization algorithm is proposed to obtain a stationary point. Simulations showcase the effectiveness of this scheme when the AR parametrization is valid.

Phase retrieval has recently attracted renewed interest. It is revisited here through a new approach based on nonconvex quadratically constrained quadratic programming (QCQP). A least-squares (LS) formulation is adopted, and a recently developed non-convex QCQP approximation technique called feasible point pursuit (FPP) is tailored to obtain a new LS-FPP phase retrieval algorithm. The Cramér-Rao bound (CRB) is also derived for phase retrieval under additive white Gaussian noise. We demonstrate through simulations that the LS-FPP method outperforms the prior art and its mean square error approaches the CRB.

Generalized canonical correlation analysis (GCCA) aims at extracting common structure from multiple 'views', i.e., high-dimensional matrices representing the same objects in different feature domains – an extension of classical two-view CCA. Existing (G)CCA algorithms have serious scalability issues, since they involve square root factorization of the correlation matrices of the views. The memory and computational complexity associated with this step grow as a quadratic and cubic function of the problem dimension (the number of samples / features), respectively. To circumvent such difficulties, we propose a GCCA algorithm whose memory and computational costs scale linearly in the problem dimension and the number of nonzero data elements, respectively. Consequently, the proposed algorithm can easily handle very large sparse views whose sample and feature dimensions both exceed 100,000 – while the current approaches can only handle thousands of features / samples. Our second contribution is a distributed algorithm for GCCA, which computes the canonical components of different views in parallel and thus can further reduce the runtime significantly (by ≥ 30% in experiments) if multiple cores are available. Judiciously designed synthetic and real-data experiments using a multilingual dataset are employed to showcase the effectiveness of the proposed algorithms.

In topic modeling, many algorithms that guarantee identifiability of the topics have been developed under the premise that there exist anchor words -- i.e., words that only appear (with positive probability) in one topic. Follow-up work has resorted to three or higher-order statistics of the data corpus to relax the anchor word assumption. Reliable estimates of higher-order statistics are hard to obtain, however, and the identification of topics under those models hinges on uncorrelatedness of the topics, which can be unrealistic. This paper revisits topic modeling based on second-order moments, and proposes an anchor-free topic mining framework. The proposed approach guarantees the identification of the topics under a much milder condition compared to the anchor-word assumption, thereby exhibiting much better robustness in practice. The associated algorithm only involves one eigen-decomposition and a few small linear programs. This makes it easy to implement and scale up to very large problem instances. Experiments using the TDT2 and Reuters-21578 corpus demonstrate that the proposed anchor-free approach exhibits very favorable performance (measured using coherence, similarity count, and clustering accuracy metrics) compared to the prior art.

Kejun Huang, Matt Gardner, Evangelos Papalexakis, Christos Faloutsos, Nikos Sidiropoulos, Tom Mitchell, Partha P. Talukdar, Xiao Fu. Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing. 2015.

Multicast beamforming is a part of the Evolved Multimedia Broadcast Multicast Service (eMBMS) in the Long-Term Evolution (LTE) standard for efficient audio and video streaming. The associated beamformer design problem has drawn considerable attention over the last decade, but existing solutions are not quite satisfactory. The core problem is NP-hard, and the available approximations leave much to be desired in terms of achieving favorable performance-complexity trade-offs, especially for online implementation. This paper introduces a new class of adaptive multicast beamforming algorithms that simultaneously cover all bases - featuring guaranteed convergence and state-of-art performance at low complexity. Each update takes a step in the direction of an inverse Signal to Noise Ratio (SNR) weighted linear combination of the SNR-gradient vectors of all users. Convergence is established by recourse to proportional fairness. Simulation results show that the proposed algorithms outperform Semi-Definite Relaxation (SDR) and Successive Linear Approximation (SLA - the prior state-of-art) at an order of magnitude lower complexity.

Wideband spectrum sensing is one of the core components of cognitive radio. A novel frugal sensing scheme was recently proposed by Mehanna et al, aiming to crowdsource spectrum sensing operations to a network of sensors transmitting randomly filtered power measurement bits to a fusion center (FC). The ambient power spectrum is then estimated at the FC using a non-parametric approach. Here, it is assumed that the primary signal admits a Moving Average (MA) parametrization, and the frugal sensing problem is revisited from a parametric spectral estimation point of view. We show that the problem of estimating admissible MA parameters (and thus the MA power spectrum) from single bit quantized data can be formulated as a non-convex Quadratically Constrained Quadratic Program (QCQP). This is NP-Hard in general, but semidefinite-relaxation (SDR) can be employed to obtain approximate solutions. Simulations reveal the superior performance of the SDR technique over the globally optimal solution obtained from the non-parametric formulation, when the MA assumption is valid.

Most tensor decomposition algorithms were developed for in-memory computation on a single machine. There are a few recent exceptions that were designed for parallel and distributed computation, but these cannot easily incorporate practically important constraints, such as nonnegativity. A new constrained tensor factorization framework is proposed in this paper, building upon the Alternating Direction method of Multipliers (ADMoM). It is shown that this simplifies computations, bypassing the need to solve constrained optimization problems in each iteration, yielding algorithms that are naturally amenable to parallel implementation. The methodology is exemplified using nonnegativity as a baseline constraint, but the proposed framework can incorporate many other types of constraints. Numerical experiments are encouraging, indicating that ADMoM-based nonnegative tensor factorization (NTF) has high potential as an alternative to state-of-the-art approaches.

Multi-dimensional arrays, or tensors, are increasingly found in fields such as signal processing and recommender systems. Real-world tensors can be enormous in size and often very sparse. There is a need for efficient, high-performance tools capable of processing the massive sparse tensors of today and the future. This paper introduces SPLATT, a C library with shared-memory parallelism for three-mode tensors. SPLATT contains algorithmic improvements over competing state of the art tools for sparse tensor factorization. SPLATT has a fast, parallel method of multiplying a matricide tensor by a Khatri-Rao product, which is a key kernel in tensor factorization methods. SPLATT uses a novel data structure that exploits the sparsity patterns of tensors. This data structure has a small memory footprint similar to competing methods and allows for the computational improvements featured in our work. We also present a method of finding cache-friendly reordering and utilizing them with a novel form of cache tiling. To our knowledge, this is the first work to investigate reordering and cache tiling in this context. SPLATT averages almost 30x speedup compared to our baseline when using 16 threads and reaches over 80x speedup on NELL-2.

How can we reverse-engineer the brain connectivity, given the input stimulus, and the corresponding brain-activity measurements, for several experiments? We show how to solve the problem in a principled way, modeling the brain as a linear dynamical system (LDS), and solving the resulting “system identification” problem after imposing sparsity and non-negativity constraints on the appropriate matrices. These are reasonable assumptions in some applications, including magnetoencephalography (MEG). There are three contributions: (a) Proof: We prove that this simple condition resolves the ambiguity of similarity transformation in the LDS identification problem; (b) Algorithm: we propose an effective algorithm which further induces sparse connectivity in a principled way; and (c) Validation: our experiments on semi-synthetic (C. elegans), as well as real MEG data, show that our method recovers the neural connectivity, and it leads to interpretable results.

Quadratically Constrained Quadratic Programming (QCQP) has a broad spectrum of applications in engineering. The general QCQP problem is NP-Hard. This article considers QCQP with Toeplitz-Hermitian quadratics, and shows that it possesses hidden convexity: it can always be solved in polynomial-time via Semidefinite Relaxation followed by spectral factorization. Furthermore, if the matrices are circulant, then the QCQP can be equivalently reformulated as a linear program, which can be solved very efficiently. An application to parametric power spectrum sensing from binary measurements is included to illustrate the results.

Quadratically constrained quadratic programs (QCQPs) have a wide range of applications in signal processing and wireless communications. Non-convex QCQPs are NP-hard in general. Existing approaches relax the non-convexity using semi-definite relaxation (SDR) or linearize the non-convex part and solve the resulting convex problem. However, these techniques are seldom successful in even obtaining a feasible solution when the QCQP matrices are indefinite. In this letter, a new feasible point pursuit successive convex approximation (FPP-SCA) algorithm is proposed for non-convex QCQPs. FPP-SCA linearizes the non-convex parts of the problem as conventional SCA does, but adds slack variables to sustain feasibility, and a penalty to ensure slacks are sparingly used. When FPP-SCA is successful in identifying a feasible point of the non-convex QCQP, convergence to a Karush-Kuhn-Tucker (KKT) point is thereafter ensured. Simulations show the effectiveness of our proposed algorithm in obtaining feasible and near-optimal solutions, significantly outperforming existing approaches.

How can we efficiently decompose a tensor into sparse factors, when the data do not fit in memory? Tensor decompositions have gained a steadily increasing popularity in data-mining applications; however, the current state-of-art decomposition algorithms operate on main memory and do not scale to truly large datasets. In this work, we propose P ar C ube , a new and highly parallelizable method for speeding up tensor decompositions that is well suited to produce sparse approximations. Experiments with even moderately large data indicate over 90% sparser outputs and 14 times faster execution, with approximation error close to the current state of the art irrespective of computation and memory requirements. We provide theoretical guarantees for the algorithm’s correctness and we experimentally validate our claims through extensive experiments, including four different real world datasets (E nron , L bnl , F acebook and N ell ), demonstrating its effectiveness for data-mining practitioners. In particular, we are the first to analyze the very large N ell dataset using a sparse tensor decomposition, demonstrating that P ar C ube enables us to handle effectively and efficiently very large datasets. Finally, we make our highly scalable parallel implementation publicly available, enabling reproducibility of our work.

Transmit beamforming is used to steer radiated power towards a receiver of interest and to limit interference to unintended receivers, thereby facilitating coexistence. Transmit beamforming requires accurate channel state information (CSI) at the transmitter, which is often difficult to acquire, particularly in cognitive underlay settings, where the primary receiver cannot be expected to cooperate with the secondary system to enable it to learn the secondary to primary crosstalk channel. This paper considers cases where it is not realistic to assume channel reciprocity, or that the receivers are capable of accurate CSI estimation and feedback-because they are legacy systems, or have limited computation/energy resources. Transmit beamforming from binary and infrequent CSI is first considered for an isolated link. An online beamforming and learning algorithm is developed using the analytic center cutting plane method and is shown to asymptotically attain optimal performance. A robust maximum-likelihood formulation is next developed to handle feedback errors and correlation drift. The setup is then generalized to a cognitive underlay setting, also exploiting the standard acknowledgement/negative-acknowledgement feedback on the reverse primary link. This is the first solution to jointly tackle secondary signal-to-noise ratio maximization and primary interference mitigation from only rudimentary CSI, without assuming channel reciprocity.

Unraveling power spectra mixtures and finding the directions of the constituent sources can enable effective spatial occupancy prediction by location-dependent combining of the recovered source power spectra; and it is also useful for primary interference avoidance. Such unmixing and direction-finding is a challenging leap beyond ordinary `aggregate' spectrum sensing. This paper presents a promising new method for blind (power) spectra separation and emitter direction finding using a network of cognitive radios. Each radio has a pair of antennas, and the baselines of different radios are aligned (e.g., using a compass), in a configuration reminiscent of classical spatial correlation-based ESPRIT. Unlike classical ESPRIT, array geometry is exploited here in the temporal correlation domain to come up with a simple and effective blind spectra separation and direction finding solution with guaranteed identifiability and robustness to noise. A notable feature is that the different radios need not be synchronized, as they do in spatial ESPRIT.

Transmit beamforming is an effective way to enhance transmission range and quality of service while limiting interference to other co-channel systems, thus facilitating easier coexistence. Transmit beamforming requires channel state information to be acquired at the receiver and fed back to the transmitter. This in turn requires a relatively complex receiver, agreement on a training protocol, and a cold-start training period during which no payload is sent to the receiver. This article explores how the transmitter can learn to beam-form on-the-fly from very low-rate channel quality indicator bits fed back from the receiver, while transmitting payload at the same time. The setup is tuned to low-latency scenarios where the receiver has limited capabilities, and is paired up opportunistically with the transmitter. Leveraging the Analytic Center Cutting Plane Method (ACCPM), an online channel correlation matrix learning method is developed, based on one-bit Signal to Noise Ratio (SNR) feedback from the receiver. The method is shown to asymptotically achieve the maximum possible SNR at the receiver (attained with perfect knowledge of the correlation matrix), starting from no channel state information. A Maximum Likelihood (ML) formulation is also developed for the case when there are feedback errors, and conditions for its asymptotic convergence are derived.

This work examines a sparse dictionary learning task - that of fitting a collection of data points, arranged as columns of a matrix, to a union of low-dimensional linear subspaces - in settings where only highly quantized (single bit) observations of the data matrix entries are available. We analyze a complexity penalized maximum likelihood estimation strategy, and obtain finite-sample bounds for the average per-element squared approximation error of the estimate produced by our approach. Our results are reminiscent of traditional parametric estimation tasks - we show here that despite the highly-quantized observations, the normalized per-element estimation error is bounded by the ratio between the number of “degrees of freedom” of the matrix and its dimension.

A parallel algorithm for low-rank tensor decomposition that is especially well-suited for big tensors is proposed. The new algorithm is based on parallel processing of a set of randomly compressed, reduced-size `replicas' of the big tensor. Each replica is independently decomposed, and the results are joined via a master linear equation per tensor mode. The approach enables massive parallelism with guaranteed identifiability properties: if the big tensor has low rank and the system parameters are appropriately chosen, then the rank-one factors of the big tensor will be exactly recovered from the analysis of the reduced-size replicas. The proposed algorithm is proven to yield memory / storage and complexity gains of order up to IJ/F for a big tensor of size I × J × K of rank F with F ≤I ≤J ≤K.

Given a simple noun such as {\em apple}, and a question such as "is it edible?", what processes take place in the human brain? More specifically, given the stimulus, what are the interactions between (groups of) neurons (also known as functional connectivity) and how can we automatically infer those interactions, given measurements of the brain activity? Furthermore, how does this connectivity differ across different human subjects?

How can we correlate the neural activity in the human brain as it responds to typed words, with properties of these terms (like ‘edible’, ‘fits in hand’)? In short, we want to find latent variables, that jointly explain both the brain activity, as well as the behavioral responses. This is one of many settings of the Coupled Matrix-Tensor Factorization (CMTF) problem. Can we accelerate any CMTF solver, so that it runs within a few minutes instead of tens of hours to a day, while maintaining good accuracy? We introduce Turbo-SMT, a meta-method capable of doing exactly that: it boosts the performance of any CMTF algorithm, by up to 200x, along with an up to 65 fold increase in sparsity, with comparable accuracy to the baseline. We apply Turbo-SMT to BrainQ, a dataset consisting of a (nouns, brain voxels, human subjects) tensor and a (nouns, properties) matrix, with coupling along the nouns dimension. Turbo-SMT is able to find meaningful latent variables, as well as to predict brain activity with competitive accuracy.

We consider the problem of estimating a deterministic unknown vector which depends linearly on$n$noisy measurements, additionally contaminated with (possibly unbounded) additive outliers. The measurement matrix of the model (i.e., the matrix involved in the linear transformation of the sought vector) is assumed known, and comprised of standard Gaussian i.i.d. entries. The outlier variables are assumed independent of the measurement matrix, deterministic or random with possibly unknown distribution. Under these assumptions we provide a simple proof that the minimizer of the Huber penalty function of the residuals converges to the true parameter vector with a$\sqrt n $-rate, even when outliers are dense, in the sense that there is a constant linear fraction of contaminated measurements which can be arbitrarily close to one. The constants influencing the rate of convergence are shown to explicitly depend on the outlier contamination level.

Non-negative matrix factorization (NMF) has found numerous applications, due to its ability to provide interpretable decompositions. Perhaps surprisingly, existing results regarding its uniqueness properties are rather limited, and there is much room for improvement in terms of algorithms as well. Uniqueness and computational aspects of NMF are revisited here from a geometrical point of view. Both symmetric and asymmetric NMF are considered, the former being tantamount to element-wise non-negative square-root factorization of positive semidefinite matrices. New and insightful uniqueness results are derived, e.g., it is shown that a sufficient condition for uniqueness is that the conic hull of the latent factors is a superset of a particular second-order cone. Checking this is shown to be NP-complete; yet it offers insights on latent sparsity, as is also shown in a new necessary condition, to a smaller extent. On the computational side, a new efficient algorithm for symmetric NMF is proposed which uses Procrustes rotations. Simulation results show promising performance with respect to the state-of-art. The new algorithm is also applied to a clustering problem for co-authorship data, yielding meaningful and interpretable results.

Wideband spectrum sensing is an important prerequisite for cognitive radio access. A network sensing scenario comprising low-end sensors is considered, with each sensor reporting a single randomly filtered power measurement bit to the fusion center (FC), which estimates the ambient power spectrum from these bits. An adaptive thresholding algorithm is proposed to improve the quality and speed of power spectrum reconstruction. Upon receipt of each new bit, the FC picks the threshold for the next sensor so as to cut off a half-space from the feasible region along its Chebyshev center. Convergence of this algorithm to the true finite-length autocorrelation is shown, whose Fourier transform yields the power spectrum estimate. To avoid the `downlink' threshold communication overhead, an alternative algorithm is proposed, where each sensor pseudo-randomly chooses its threshold from a suitable distribution, and the FC judiciously polls sensors to form its power spectrum estimate.

Recent literature on robust statistical inference suggests that promising outlier rejection schemes can be based on accounting explicitly for sparse gross errors in the modeling, and then relying on compressed sensing ideas to perform the outlier detection. In this paper, we consider two models for recovering a sparse signal from noisy measurements, possibly also contaminated with outliers. The models considered here are a linear regression model, and its natural one-bit counterpart where measurements are additionally quantized to a single bit. Our contributions can be summarized as follows: We start by providing conditions for identification and the Cramér-Rao Lower Bounds (CRLBs) for these two models. Then, focusing on the one-bit model, we derive conditions for consistency of the associated Maximum Likelihood estimator, and show the performance of relevant l1-based relaxation strategies by comparing against the theoretical CRLB.

Back-Pressure Power Control (BPPC) is a cross-layer network optimization policy that uses power control at the physical layer to facilitate efficient routing of packets at the network layer. The starting point of this paper is that interference cancellation can be judiciously employed together with power control to further enhance network throughput. Effective cancellation requires that the interfering signal can be reliably decoded, implying that power control and interference cancellation are tightly coupled. This leads to a joint Back-Pressure Power Control and Interference Cancellation (BPPC-IC) problem formulation, with the pragmatic constraint that each receiver can cancel at most one interfering signal. This problem is shown to be NP-hard, and two approximate solutions are proposed based on successive geometric programming approximation, and an extended weighted minimum mean squared error (WMMSE) reformulation, respectively. A simpler approximation based on stochastic exploration of the control space is also considered. Simulation results demonstrate that joint optimization of power control and interference cancellation pays off, enabling considerably higher network throughput, and lower average delay due to reduced backlogs.

A key problem in wireless networking is how to choose a link activation schedule and associated powers in concert with routing decisions to optimize throughput. Back-pressure control policies are optimal in this context, but the underlying power control problem is non-convex. Back-pressure power control (BPPC) was recently shown to be NP-hard, yet amenable to successive convex approximation strategies that deliver manifold improvements in end-to-end throughput relative to the prior art in wireless networking. A drawback is that existing implementations are centralized, whereas practical power control has to be distributed across the network. This paper fills this gap by developing a distributed version of the core step of successive convex approximation of the BPPC problem, building upon the Alternating Direction Method of Multipliers (ADMoM). The resulting protocol enjoys favorable properties relative to dual decomposition - based implementations, and allows tight approximation of the BPPC objective in all interference regimes. Judicious simulations reveal that the proposed algorithm matches the performance of its centralized counterpart, as well as pertinent trade-offs in terms of the design parameters.

For linear models, compressed sensing theory and methods enable recovery of sparse signals of interest from few measurements-in the order of the number of nonzero entries as opposed to the length of the signal of interest. Results of similar flavor have more recently emerged for bilinear models, but no results are available for multilinear models of tensor data. In this contribution, we consider compressed sensing for sparse and low-rank tensors. More specifically, we consider low-rank tensors synthesized as sums of outer products of sparse loading vectors, and a special class of linear dimensionality-reducing transformations that reduce each mode individually. We prove interesting “oracle” properties showing that it is possible to identify the uncompressed sparse loadings directly from the compressed tensor data. The proofs naturally suggest a two-step recovery process: fitting a low-rank model in compressed domain, followed by per-mode decompression. This two-step process is also appealing from a computational complexity and memory capacity point of view, especially for big tensor datasets.

Cross-layer design and operation of wireless networks has attracted significant interest in the last decade, yet some basic problems in the area remain unsolved. In this paper, we consider the joint routing and power control problem, and specifically how to choose transmission powers at the physical layer to maximize stable end-to-end throughput at the network layer for a multi-hop wireless network. This is the back-pressure power control (BPPC) problem. Earlier work had recognized that BPPC is a non-convex problem, and suggested relatively simple suboptimal strategies. Here we show that BPPC is NP-hard. This is a negative result, which however comes with a positive flip side: drawing from related developments in the digital subscriber line (DSL) literature, we devise effective ways to approximate it. We report substantial improvements in transport capacity relative to the earlier state of art, as illustrated in pertinent simulations.

The K-means clustering problem seeks to partition the columns of a data matrix in subsets, such that columns in the same subset are 'close' to each other. The co-clustering problem seeks to simultaneously partition the rows and columns of a matrix to produce 'coherent' groups called co-clusters. Co-clustering has recently found numerous applications in diverse areas. The concept readily generalizes to higher-way data sets (e.g., adding a temporal dimension). Starting from K-means, we show how co-clustering can be formulated as constrained multilinear decomposition with sparse latent factors. In the case of three- and higher-way data, this corresponds to a PARAFAC decomposition with sparse latent factors. This is important, for PARAFAC is unique under mild conditions and sparsity further improves identifiability. This allows us to uniquely unravel a large number of possibly overlapping co-clusters that are hidden in the data. Interestingly, the imposition of latent sparsity pays a collateral dividend: as one increases the number of fitted co-clusters, new co-clusters are added without affecting those previously extracted. An important corollary is that co-clusters can be extracted incrementally; this implies that the algorithm scales well for large datasets. We demonstrate the validity of our approach using the ENRON corpus, as well as synthetic data.

Power control is important in interference-limited cellular, ad-hoc, and cognitive underlay networks, when the objective is to ensure a certain quality of service to each connection. Power control has been extensively studied in this context, including distributed algorithms that are particularly appealing in ad-hoc and cognitive settings. A long-standing issue is that the power control problem may be infeasible, thus requiring appropriate admission control. The power and admission control parts of the problem are tightly coupled, but the joint optimization problem is NP-hard. We begin with a convenient reformulation which enables a disciplined convex approximation approach. This leads to a centralized approximate solution that is numerically shown to outperform the prior art, and even yield close to optimal results in certain cases - at affordable complexity. The issue of imperfect channel state information is also considered. A distributed implementation is then developed, which alternates between distributed approximation and distributed deflation - reaching consensus on a user to drop, when needed. Both phases require only local communication and computation, yielding a relatively lightweight distributed algorithm with the same performance as its centralized counterpart.

Frequency hopping (FH) signals have well-documented merits for commercial and military applications due to their near-far resistance and robustness to jamming. Estimating FH signal parameters (e.g., hopping instants, carriers, and amplitudes) is an important and challenging problem, but optimum estimation incurs an unrealistic computational burden. The spectrogram has long been the nonparametric estimation workhorse in this context, followed by line spectra refinement. The problem is that hop timing estimates derived from the spectrogram are coarse and unreliable, thus severely limiting performance. In this paper we take a fresh look at this problem, based on sparse linear regression (SLR). At any point in time, there are only few active carriers; and carrier hopping is rare for slow FH. Using a dense frequency grid, we formulate the problem as under-determined linear regression with a dual sparsity penalty, and develop an exact solution using the alternating direction method of multipliers (ADMoM). Simulations demonstrate that the developed technique outperforms spectrogram-based methods, especially with regards to hop timing estimation, which is the crux of the problem.

Power control is important in interference-limited cellular, ad-hoc, and cognitive wireless networks, when the objective is to ensure a certain quality of service to each connection. Power control has been extensively studied in this context, including distributed algorithms that are particularly appealing in ad-hoc and cognitive settings. A long-standing issue is that the power control problem may be infeasible, thus requiring appropriate admission control. The power and admission control parts of the problem are tightly coupled, but the joint problem is NP-hard. In recent work, we developed a convex relaxation-based deflation approach to the joint problem, which was shown to outperform the prior art, and yield close to optimal solutions at moderate computational cost. In this paper, we derive a distributed version of our joint power and admission control algorithm. The algorithm alternates between distributed approximation and distributed deflation - reaching consensus on a user to drop, when needed. Both phases require only local communication and computation, yielding a relatively lightweight distributed algorithm which also attains close to optimal performance.

Co-clustering can be viewed as a two-way (bilinear) factorization of a large data matrix into dense/uniform and possibly overlapping sub-matrix factors (co-clusters). This combinatorially complex problem emerges in several applications, including behavior inference tasks encountered with social networks. Existing co-clustering schemes do not exploit the fact that overlapping factors are often sparse, meaning that their dimension is considerably smaller than that of the data matrix. Based on plaid models which allow for overlapping submatrices, the present paper develops a sparsity-cognizant overlapping co-clustering (SOC) approach. Numerical tests demonstrate the ability of the novel SOC scheme to globally detect multiple overlapping co-clusters, outperforming the original plaid model algorithms which rely on greedy search and ignore sparsity.

We present a frequency-domain technique based on PARAllel FACtor (PARAFAC) analysis that performs multichannel blind source separation (BSS) of convolutive speech mixtures. PARAFAC algorithms are combined with a dimensionality reduction step to significantly reduce computational complexity. The identifiability potential of PARAFAC is exploited to derive a BSS algorithm for the under-determined case (more speakers than microphones), combining PARAFAC analysis with time-varying Capon beamforming. Finally, a low-complexity adaptive version of the BSS algorithm is proposed that can track changes in the mixing environment. Extensive experiments with realistic and measured data corroborate our claims, including the under-determined case. Signal-to-interference ratio improvements of up to 6 dB are shown compared to state-of-the-art BSS algorithms, at an order of magnitude lower computational complexity.

The problem of transmit beamforming for single-group multicasting is considered, where the objective is to transmit common information to a (large) number of users. The transmitter is assumed to have accurate downlink channel state information (CSI) for all users, and the objective is to design the beamformer weights to minimize the total transmitted power subject to meeting the quality-of-service (QoS) constraints of all users. This is an NP-hard problem that has recently drawn considerable interest (e.g., in the context of UMTS-LTE / E-MBMS). Several channel orthogonalization-based methods are proposed to solve this problem in an approximate way. Our techniques are shown to offer an improved performance-to-complexity tradeoff as compared to the original semidefinite relaxation (SDR) based multicasting technique.

In this paper, we show that the problem of detection and localization of multiple targets in a bistatic MIMO radar system can be solved by parallel factor (PARAFAC) analysis. Our method is deterministic and fully capitalizes on the strong algebraic structure of the received data, where the radar cross section (RCS) fluctuation is not regarded as a nuisance parameter but rather as a source of time diversity. Simulation results show that our technique outperforms existing beamforming-based radar imaging methods at a lower complexity.

The multicast beamforming problem is considered from the viewpoint of minimizing outage probability subject to a transmit power constraint. The main difference with the point-to-point transmit beamforming problem is that in multicast beamforming the channel is naturally modeled as a Gaussian mixture, as opposed to a single Gaussian distribution. The Gaussian components in the mixture model user clusters of different means (locations) and variances (spreads). It is shown that minimizing outage probability subject to a transmit power constraint is an NP-hard problem when the number of Gaussian kernels, J, is greater than or equal to the number of transmit antennas, N. Through dimensionality reduction, it is also shown that the problem is practically tractable for 2 - 3 Gaussian kernels. An approximate solution based on the Markov inequality is also proposed. This is simple to compute for any J and N, and often works well in practice.

Crosstalk interference is the limiting factor in transmission over copper lines. Crosstalk cancellation techniques show great potential for enabling the next leap in DSL transmission rates. An important issue is the effect of finite world length on performance. In this paper we provide an analysis of the performance of linear zero-forcing precoders, used for crosstalk compensation, in the presence of quantization noise. We quantify analytically the trade off between quantization level and transmission rate degradation. We demonstrate, through simulations on real lines, the accuracy of our estimates. Finally, we show how to use these estimates as a design tool for DSL linear crosstalk precoders.

Transmit beamforming for physical layer multicasting is emerging as an appealing transmission modality for next-generation cellular wireless systems, notably UMTS-LTE. Optimal design of the transmit beamformer(s) from a quality of service perspective is a hard computational problem; however, convex approximation tools have been shown to yield high-quality approximate solutions. Recently, Lozano proposed a particularly simple adaptive multicast beamforming algorithm that aims to serve a certain percentage of users. In parallel, convex approximation algorithms were developed for the more general problem of joint co-channel multicast beamforming and admission control. In this paper, we focus on the important (in view of recent standardization activity) special case of a single multicast group, and put the two approaches to the test. Through simple examples, we pinpoint issues regarding convergence of Lozano's algorithm. In numerical experiments with measured channel data, we show that a convex approximation approach is preferable performance- wise. At the same time, we find merits in the simplicity of Lozano's approach, and suggest a way to improve its performance.

This work establishes the effectiveness of parallel factor (PARAFAC) analysis in blind speech separation (BSS) problems. The BSS problem is formulated as a conjugate-symmetric PARAFAC model that is fitted optimally, using an efficient alternating least-squares algorithm that converges monotonically. The identifiability properties of the model are also presented, revealing the much broader identifiability potential of joint-diagonalization- based BSS methods. In order to focus on estimation performance, perfect resolution of the permutation ambiguity is assumed. Simulations under varying reverberation conditions and comparison with previous estimation methods that are widely used in BSS problems demonstrate significant performance gains. Signal-to- interference (SIR) ratio improvement of over 27 dB is achieved using PARAFAC. Average SIR gains of 2.5 and 6.3 dB are achieved compared to state-of-the-art FastICA[2] and FDSOS (Parra's)[5] estimation algorithms, respectively.

Multiuser downlink beamforming under quality of service (QoS) constraints has attracted considerable interest in years, because it is particularly appealing from a network operator's perspective (e.g., UMTS, 802.16e). When there are many co-channel users and/or the service constraints are stringent, the problem becomes infeasible and some form of admission control is necessary. We advocate a cross-layer approach to joint multiuser transmit beamforming and admission control, aiming to maximize the number of users that can be served at their desired QoS. It is shown that the core problem is NP-hard, yet amenable to convex approximation tools. Two computationally efficient convex approximation algorithms are proposed: one is based on semidefinite relaxation of an equivalent problem reformulation; the other takes a penalized second-order cone approach. Their performance is assessed in a range of experiments, using both simulated and measured channel data. In all experiments considered, the proposed algorithms work remarkably well in terms of the attained performance-complexity trade-off, consistently exhibiting close to optimal performance at an affordable computational complexity.

A novel framework was introduced recently for stochastic routing in wireless multihop networks, whereby each node selects a neighbor to forward a packet according to a probability distribution. Generalizing (deterministic) shortest path routing, stochastic routing offers greater flexibility that matches the random nature of wireless links. Consider the pairwise reliability matrix R, whose (i, j)-th entry Rijrepresents the probability that a packet transmitted from the j-th user Ujis correctly received by the i-th user Ui. Using R to capture physical layer aspects of the wireless medium, several rate-oriented stochastic routing formulations can be reduced to centrally solvable convex optimization problems. The present paper, introduces distributed algorithms that find optimal routing probabilities without the burden of collecting R at a central node and then percolating the resulting routing probabilities through network nodes. The resultant schemes are distributed in the sense that: (i) terminal Ujhas access only to the j-th row and column of R; and (ii) Ujinterchanges variables only with those single-hop neighbors having positive probability of decoding its packets. The distributed algorithms are built by recasting the optimization problems and applying dual decomposition techniques. Since iterates obtained via dual decomposition do not always converge to centralized optimal routing probabilities, two known regularization approaches are further invoked, namely the method of multipliers (MoM) and the alternating-direction MoM. Convergence to the optimal routing matrix is then guaranteed under mild conditions. Many rate-oriented optimality criteria of practical interest can be addressed by the distributed framework, including maximization of: (i) the minimum rate; (ii) a weighted sum of rates; (iii) the product of rates; and (iv) the source's rate in a relay network. Robustness of the distributed algorithms is tested with respect to "topological" changes, communication errors and node mobility.

Multiuser downlink beamforming under quality of service (QoS) constraints has attracted considerable interest in recent years, because it is particularly appealing from a network operator's perspective (e.g., UMTS, 802.16e). When there are many co-channel users and/or the service constraints are stringent, the problem becomes infeasible and some form of admission control is necessary. We advocate a cross-layer approach to joint multiuser transmit beamforming and admission control, aiming to maximize the number of users that can be served at their desired QoS. The core problem is NP-hard, yet amenable to convex approximation tools. We propose a computationally efficient semidefinite relaxation algorithm which works remarkably well in a range of experiments, using both simulated and measured channel data.

We introduce distributed algorithms to find rate-optimal routes based on local knowledge of the pairwise error probability (reliability) matrix. The distributed algorithms are built by (re)-formulating optimization problems amenable to application of dual decomposition techniques. Convergence of our algorithms to the optimal routing matrix is guaranteed under mild conditions. Many rate-optimality criteria of practical interest can be casted in our framework including maximization of: i)worst user's rate; ii) weighted sum of rates; iii) product of rates; and iv) relay network rate. We test robustness of our algorithms to node mobility.

We introduce a novel approach to multi-hop routing in wireless networks. Instead of the usual graph description we characterize the network by the packet delivery ratio matrix whose entries represent the probability that a given node decodes the packet transmitted by any other node. The model lends itself naturally to the formulation of stochastic routing protocols in which packets are randomly routed to neighboring nodes; and routing algorithms search for a matrix of routing probabilities according to properly defined optimality criteria. The goal of the paper is to show that this novel framework offers a useful model to aid in the design of optimal routing algorithms. In particular, it is established that: (i) performance is improved with respect to graph descriptions; and (ii) optimal routes can be obtained as the solution of optimization problems, many of which turn out to be convex and can thus be solved in polynomial time using interior point methods.

Well appreciated at the physical layer, user cooperation is introduced here as a diversity enabler for wireless random access (RA) at the medium access control sublayer. This is accomplished through a two-phase protocol in which active users start with a low power transmission attempting to reach nearby users and follow up with a high power transmission in cooperation with the users recruited in the first phase. We show that such a cooperative protocol yields a significant increase in throughput. Specifically, we prove that for networks with a large number of users, the throughput of a cooperative wireless RA network operating over Rayleigh-fading links approaches the throughput of an RA network operating over additive white Gaussian noise links—thus justifying the title of the paper. The message borne out of this result is that user cooperation offers a viable choice for migrating diversity benefits to the wireless RA regime, thus bridging the gap to wireline RA networks, without incurring a bandwidth or energy penalty.

We consider the problem of transmit beamforming to multiple co-channel multicast groups. Since the direct minimization of transmit power while guaranteeing a prescribed minimum signal to interference plus noise ratio (SINR) at each receiver is nonconvex and NP-hard, we present convex SDP relaxations of this problem and study when such relaxations are tight. Our results show that when the steering vectors for all receivers are of Vandermonde type (such as in the case of a uniform linear array and line-of-sight propagation), a globally optimum solution to the corresponding transmit beamforming problem can be obtained via an equivalent SDP reformulation. We also present various robust formulations for the problem of single-group multicasting, when the steering vectors are only approximately known. Simulation results are presented to illustrate the effectiveness of our SDP relaxations and reformulations.

We propose a new two-step frequency domain algorithm for blind speech separation (BSS) for unknown channel order. This new approach employs parallel factor analysis (PARAFAC) to separate the speech signals and a novel integer-least-squares-based method for matching the arbitrary permutations in the frequency domain. The proposed algorithm offers guaranteed convergence and good separation performance, measured both quantitatively and in subjective tests. Performance gains in signal-to-interference ratio of up to 10 db are achieved for certain source-sensor geometries

The problem of tracking the frequency and complex amplitude of a frequency-hopped complex sinusoid is considered, using a novel stochastic state-space formulation and particle filtering tools. The problem is of considerable interest for interference mitigation in frequency-hopped wireless networks, and in military communications. The proposed particle filtering approach has a number of desirable features. It affords high-resolution estimates of carrier frequency and hop timing, manageable complexity (linear in the number of processed samples), and flexibility in tracking signals with irregular hopping patterns due to intentional timing jitter. The proposed state-space model is not only parsimonious, but fortuitous as well: it turns out that the associated optimal importance function can be computed in closed form, and thus samples from it can be drawn using rejection techniques. Both prior and optimal importance sampling versions are developed and illustrated in pertinent simulations

A new and conceptually simple semidefinite relaxation approach is proposed for MIMO detection in communication systems employing high-order QAM constellations. The new approach affords improved detection performance compared to existing solutions of comparable worst-case complexity order, which is nearly cubic in the dimension of the transmitted symbol vector and independent of the constellation order for uniform QAM, or affine in the constellation order for nonuniform QAM

Multiple-input multiple-output (MIMO) communication has recently attracted considerable interest for transmission over multiple twisted copper pairs in a common binder. The motivation is to overcome the limitations imposed by crosstalk, and thus boost capacity. Far-end crosstalk (FEXT) is the dominant impairment in frequency-division duplex (FDD) digital subscriber line (DSL) systems. While the per-tone MIMO channel matrix is diagonally dominated in this context, noise is colored due to alien FEXT, which is particularly pronounced for short DSL loops - such as those encountered in fiber-to-the-curb (FTTC) or fiber-to-the-basement (FTTB) architectures. This calls for effective multiuser detection strategies at the receiver. We test three candidate detection algorithms (probabilistic data association, sphere decoding, and a recently proposed hybrid thereof) using measured channel data for 300 meter cable, and a fixed upper bound on vector decoding complexity. The results indicate that, when half of the loops in the binder are coordinated, contrary to the case of Rayleigh fading wireless channels, the sphere decoder provides the best performance, even when a pragmatic complexity restriction is employed.

Cooperative wireless communication systems have attracted much attention in recent years, due to the diversity advantage they can afford. Existing cooperative transmission modalities have been developed in conjunction with fixed-rate multiplexing based on TDMA, CDMA or FDMA. We advocate user cooperation as the method of choice for enabling diversity in wireless random access networks. The specific protocol developed herein exploits the fact that user cooperation can be viewed as a form of multipath, and capitalizes on the suitability of long pseudo-noise (PN) spreading codes for dealing with multipath channels. Analysis and numerical results confirm that throughput increases considerably when random access via spread-spectrum slotted Aloha protocols is aided by user collaboration.

Random access Aloha protocols have well documented merits in terms of simplicity and favorable delay-throughput trade-off under moderate bursty traffic loads. Short spreading codes have been used in conjunction with random access to endow Aloha with benefits originating from spread-spectrum communications. Instead of short, symbol-periodic spreading, this paper considers long pseudo-random (PN) packet-periodic sequences in the context of spread-Aloha and establishes that long PN codes increase the maximum stable throughput by reducing the probability of collisions. Relying on a dominant system approach, we analyze the resultant throughput and demonstrate that increasing the PN code length quickly transforms the collision-limited channel to an interference-limited one. In particular, we investigate how throughput depends on user load and packet length. Finally, we discuss synchronization issues and provide corroborating numerical results.

A hybrid probabilistic data association (PDA)-sphere decoding (SD) algorithm is proposed for signal detection in multiple-input-multiple-output (MIMO) systems. The key idea is to reduce the dimension of the problem solved via SD by first running a single stage of the PDA to fix symbols that can be decoded with high reliability. Simulations under a multiple antenna Rayleigh fading scenario show that this two-step algorithm attains a considerably better performance-complexity tradeoff than SD and PDA for low to moderate signal-to-noise ratio (SNR) or higher problem dimensions.

We assess the capacity potential of very short very-high data-rate digital subscriber line loops using full-binder channel measurements collected by France Telecom R&D. Key statistics are provided for both uncoordinated and vectored systems employing coordinated transmitters and coordinated receivers. The vectoring benefit is evaluated under the assumption of transmit precompensation for the elimination of self-far-end crosstalk, and echo cancellation of self-near-end crosstalk. The results provide useful bounds for developers and providers alike.

With the rapid growth of frequency-hopped (FH) wireless networks, interference due to frequency collisions has become one of the main performance-limiting challenges. This paper proposes a novel multiuser detection method for joint hop timing and frequency estimation, which is capable of unraveling and demodulating multiple FH transmissions in the presence of collisions and unknown hop patterns without retransmission. The method is based on the principle of dynamic programming (DP) coupled with two-dimensional harmonic retrieval (2-D HR) or low-rank trilinear decomposition, and it remains operational even with multiple unknown hop rates, frequency offsets, and asynchronism. The model is based on frequency-shift keying (FSK) and phase-shift keying (PSK) modulation, but the algorithms are also evaluated with Gaussian minimum-shift keying (GMSK) modulation and shown to be robust.

The problem of simultaneous multiuser downlink beamforming has recently attracted significant interest in both the information theory and signal processing communities. The idea is to employ a transmit antenna array to create multiple 'beams' directed towards the individual users, and the aim is to increase throughput, measured by sum capacity. Optimal solutions to this problem require convex optimization and so-called dirty paper (DP) precoding for known interference; these are prohibitively complex for actual online implementation at the base station. Motivated by recent results by H. Viswanathan et al. (see IEEE J. Sel. Areas in Commun., vol.21, no.5, p.802-11, 2003) and G. Caire and S. Shamai (see IEEE Trans. Inf. Theory, vol.49, no.7, p.1691-706, 2003), we propose a computationally simple user selection method coupled with zero-forcing beamforming. Our results indicate that the proposed method attains a significant fraction of sum capacity, and thus offers an attractive alternative to DP-based schemes.

Multidimensional harmonic retrieval (HR) problems often appear in the context of MIMO wireless channel sounding. In particular, for a double-directional parametric MIMO channel model with uniform linear transmit and receive arrays, and a fixed wireless scenario (static - no Doppler), fitting the channel model parameters amounts to a 3D harmonic retrieval problem. For this latter problem, we develop two new algorithms. One is based on conjugate-folding of the 3D data and reduction to an eigenvalue decomposition problem; the other on a 3D version of the rank reduction estimator (RARE) applied to a subspace extracted from a single data snapshot, using 3D conjugate-folding. Both algorithms remain operative close to the best known model identifiability boundary. The two algorithms are compared via pertinent simulations.

Parallel factor (PARAFAC) analysis is an extension of low-rank matrix decomposition to higher-way arrays. It decomposes a given array in a sum of multilinear terms. PARAFAC analysis generalizes and unifies common array processing models (like joint diagonalization and ESPRIT); it has found numerous applications from blind multiuser detection and multi-dimensional harmonic retrieval to clustering and nuclear magnetic resonance. The prevailing fitting algorithm in all these applications is based on alternating least squares (ALS) optimization, which is matched to Gaussian noise. In many cases, however, measurement errors are far from being Gaussian. We develop an iterative algorithm for least absolute error fitting of general multilinear models, based on efficient interior point methods for linear programming (LP). We also benchmark its performance in Laplacian, Cauchy, and Gaussian noise environments, versus the respective CRBs and the commonly used ALS algorithm.

Fair queueing (FQ) algorithms, which have been proposed for quality of service (QoS) wireline/wireless networking, rely on the fundamental idea that the service rate allocated to each user is proportional to a positive weight. Targeting wireless data networks with a multicode CDMA-based physical layer, we develop FQ with time-varying weight assignment in order to minimize the queueing delays of mobile users. Applying dynamic programming, we design a computationally efficient algorithm which produces the optimal service rates while obeying 1) constraints imposed by the underlying physical layer and 2) QoS requirements. Furthermore, we study how information about the underlying channel quality can be incorporated into the scheduler to improve network performance. Simulations illustrate the merits of our designs.

We consider a wireless data network setup that provides scalability and robustness to node failures, while achieving high throughput and low mean delay. A semi-ad-hoc frequency-hopped (FH) network diversity multiple access (NDMA) scheme is proposed. In this scheme, nodes are dynamically organized into clusters, where each cluster operates under NDMA random access protocol with FH on a per packet slot basis using a cell-specific FH pattern. In a moderately loaded system, collisions between packets from different clusters are not negligible. In order to guard against such collisions, we propose NDMA with a fixed retransmission margin of M slots. For this system, we derive a sufficient condition for stability using a deterministic fluid arrivals model. We also analyze the steady-state, and obtain useful formulas for approximating mean packet delay.

A noncoherent reception scheme is developed for joint blind estimation of hop timing, hop frequency and direction-of-arrival (DOA) of frequency hopped signals over multipath fading channels. Based on the principle of dynamic programming and 2-dimensional harmonic retrieval, the method does not require knowledge of users' hop codes, and it remains operational even with multiple (unknown) hop rates, frequency offsets, and asynchronism. The model is based on FSK, but the scheme is also evaluated with GMSK modulation and shown to be robust.

Given a noisy sequence of (possibly shifted) integer multiples of a certain period, it is often of interest to estimate the period (and offset). With known integer regressors, the problem is classical linear regression. In many applications, however, the actual regressors are unknown; only categorical information (i.e., the regressors are integers) and, perhaps, loose bounds are available. Examples include hop timing estimation, pulse repetition interval (PRI) analysis, and passive rotating-beam radio scanning. With unknown regressors, this seemingly simple problem exhibits many surprising twists. Even for small sample sizes, a proposed quasi-maximum likelihood approach essentially meets the clairvoyant CRB at moderately high SNR - the latter assumes knowledge of the unknown regressors. This is quite unusual, and it holds despite the fact that our algorithm ignores noise color. We outline analogies and differences between our problem and classical linear regression and harmonic retrieval, and corroborate our findings with careful simulations.

In wireless cellular communications, accurate local mean (shadow) power estimation performed at a mobile station is important for use in power control, handoff, and adaptive transmission. Window-based weighted sample average shadow power estimators are commonly used due to their simplicity. In practice, the performance of these estimators degrades severely when the window size deviates beyond a certain range. The optimal window size for window-based estimators is hard to determine and track in practice due to the continuously changing fading environment. Based on a first-order autoregressive model of the shadow process, we propose a scalar Kalman-filter-based approach for improved local mean power estimation, with only slightly increased computational complexity. Our analysis and experiments show promising results.

A class of collision resolution protocols [(B)NDMA] has recently been introduced for slotted packet multiple access, building on the concept of retransmission diversity. These protocols offer the means to improve upon random splitting-based collision resolution protocols, at a moderate complexity cost. However, stability of these protocols has not been established, and the available steady-state analysis is restricted to symmetric (common-rate) systems. In this paper, we formally analyze stability of (B)NDMA, by providing sufficient conditions that guarantee ergodicity of the associated embedded Markov chain. A key tool is the concept of dominant system, which we borrow from the literature on stability analysis of finite population slotted ALOHA. After establishing stability, we take a fresh look at steady-state analysis, bypassing the earlier generating function approach, using instead only balance equations which hold for a stable system. This approach allows dealing with asymmetry (multirate systems), yielding expressions for throughput and delay per queue. Finally, we generalize BNDMA and the associated stability analysis to multicode systems.

In the context of multiuser detection for the DS-CDMA uplink, out-of-cell interference is usually treated as Gaussian noise, possibly mitigated by overlaying a long random cell code on top of symbol spreading. Different cells use statistically independent long codes, thereby providing means for statistical out-of-cell interference suppression. When the total number of (in-cell plus out-of-cell) users is less than the spreading gain, subspace identification techniques are applicable. If the base station is equipped with an antenna array, then completely blind identification is possible via three-dimensional low-rank decomposition. This works with more users than spreading and antennas, but a purely algebraic solution is missing. In this paper, we develop an algebraic solution under the premise that the codes of the in-cell users are known. The codes of out-of-cell users and all array steering vectors are unknown. In this pragmatic scenario, we show that in addition to algebraic solution, better identifiability is possible. Our approach yields the best known identifiability result for three-dimensional low-rank decomposition when one of the three component matrices is partially known, albeit non-invertible.

In a recent paper, it has been shown that up to ⌊K over 2⌋ ⌈L over 2⌉two-dimensional (2-D) exponentials are almost surely identifiable from a K × L mixture, assuming regular sampling at or above Nyquist in both dimensions. This holds for damped or undamped exponentials. In this paper, we show that up to ⌊K over 2⌋ ⌈L over 2⌉ undamped exponentials can be uniquely recovered almost surely. Multidimensional conjugate folding is used to achieve this improvement. The main result is then generalized to N > 2 dimensions. The gain is interesting from a theoretical standpoint, but also for small 2-D sensor arrays or higher dimensions and odd sample sizes. Also important is that the proof implies an algebraic retrieval algorithm, called the MDF algorithm, which outperforms some of the best known algebraic 2-D harmonic retrieval algorithms. We illustrate this by comparing to MEMP, JAFE, and also our own earlier multidimensional embedding (MDE) algorithm.

This paper deals with the multiuser medium access problem in the packet radio environment. Under the framework of network diversity multiple access (NDMA), a previously proposed medium access method, a blind collision resolution scheme is proposed employing rotational invariance and factor analysis techniques. The proposed approach (dubbed B-NDMA for blind NDMA) overcomes the difficulty of orthogonal identification codes required by the original protocol, thereby improving channel utilization and system capacity, while being insensitive to multipath effects and synchronization errors. Performance issues of the proposed technique are addressed both analytically and numerically.

Two-dimensional (2-D) and more generally multidimensional harmonic retrieval is of interest in a variety of applications. The associated identifiability problem is key in understanding the fundamental limitations of parametric high-resolution methods. In the 2-D case, existing identifiability results indicate that, assuming sampling at Nyquist or above, the number of resolvable exponentials is proportional to I+J, where I is the number of (equispaced) samples along one dimension, and J likewise for the other dimension. We prove that the number of resolvable exponentials is roughly IJ/4, almost surely. This is not far from the equations-versus-unknowns bound of IJ/3. We then generalize the result to the N-D case for any N>2, showing that, under quite general conditions, the number of resolvable exponentials is, proportional to the total sample size, hence grows exponentially with the number of dimensions.

A two-stage blind multiuser antenna array detector is proposed for the uplink of a wideband CDMA system subject to large delay spread. It is shown that it is possible to identify the symbols of all users without knowledge of their codes, channels, or directions. The key idea is that low-rank decomposition of the three-dimensional (3-D) received data array can reduce the FIR multiple-input multiple-output (FIR-MIMO) CDMA problem into standard FIR single-input multiple-output (FIR-SIMO) problems.

The present a novel class of multidimensional orthogonal FM transforms. The analysis suggests a novel signal-adaptive FM transform possessing interesting energy compaction properties. We show that the proposed signal-adaptive FM transform produces point spectra for multidimensional signals with uniformly distributed samples. This suggests that the proposed transform is suitable for energy compaction and subsequent coding of broadband signals and images that locally exhibit significant level diversity. We illustrate these concepts with simulation experiments.

Consider a sum of F exponentials in N dimensions, and let I/sub n/ be the number of equispaced samples taken along the nth dimension. It is shown that if the frequencies or decays along every dimension are distinct and /spl Sigma//sub n=1//sup N/ I/sub n//spl ges/2F+(N-1), then the parameterization in terms of frequencies, decays, amplitudes, and phases is unique. The result can be viewed as generalizing a classic result of Caratheodory to N dimensions. The proof relies on a recent result regarding the uniqueness of low-rank decomposition of N-way arrays.

Low-rank trilinear and quadrilinear decomposition is shown to underlie the basic model for deterministic blind beamforming (DBB) in the presence of incoherent multipath with small delay spread. Quadrilinear regression is proposed for simultaneously estimating all model parameters and compared to the column span method of van der Veen (1998). A derivation and discussion of pertinent Cramer-Rao bounds for the trilinear model, and comparison of trilinear regression performance to the CRB are also included. These are of interest beyond the application scope of this paper.

Blind separation of communication signals invariably relies on some form(s) of diversity to overdetermine the problem and thereby recover the signals of interest. More often than not, linear (e.g., spreading) diversity is employed, i.e., each diversity branch provides a linear combination of the unknown signals, albeit with possibly unknown weights. If multiple forms of linear diversity are simultaneously available, then the resulting data exhibit multilinear structure, and the blind recovery problem can be shown to be tantamount to low-rank decomposition of the multi-dimensional received data array. This paper generalizes Kruskal's fundamental result on the uniqueness of low-rank decomposition of 3-way arrays to the case of multilinear decomposition of 4- and higher-way arrays. The result characterizes diversity combining for blind identifiability when N forms of linear diversity are available; that is the balance between different forms of diversity that guarantees blind recovery of all signals involved.

This paper explores how joint network and spatial diversity can be employed to improve the throughput/delay performance of packet radio systems. In the context of the recently proposed network diversity multiple access (NDMA) technique, the challenges and advantages of using antenna arrays at the base station to complement network-assisted diversity are investigated. It is shown that remarkable improvement of the system performance can be achieved by combining network and spatial diversity. A blind method based on PARAFAC analysis tools is proposed to solve the collision resolution problem under joint network/spatial diversity. The method is also applicable to, e.g., joint network/spreading diversity.

In many applications, the data of interest comprises multiple sequences that evolve over time. Examples include currency exchange rates and network traffic data. We develop a fast method to analyze such co-evolving time sequences jointly to allow (a) estimation/forecasting of missing/delayed/future values, (b) quantitative data mining, and (c) outlier detection. Our method, MUSCLES, adapts to changing correlations among time sequences. It can handle indefinitely long sequences efficiently using an incremental algorithm and requires only a small amount of storage and less I/O operations. To make it scale for a large number of sequences, we present a variation, the Selective MUSCLES method and propose an efficient algorithm to reduce the problem size. Experiments on real datasets show that MUSCLES outperforms popular competitors in prediction accuracy up to 10 times, and discovers interesting correlations. Moreover, Selective MUSCLES scales up very well for large numbers of sequences, reducing response time up to 110 times over MUSCLES, and sometimes even improves the prediction quality.

A spatial domain watermarking algorithm for still images is proposed in this paper. The watermarks are generated by combining scaled versions of 2-D chaotic signals, in order to attain a self-similar structure. In addition, the 2-D chaotic signal generation procedure contains operations which ensure that lowpass watermarks are obtained. Such characteristics (lowpass spectrum, self-similarity) enable robustness against compression, lowpass filtering or, generally, distortions of lowpass nature, as well as, cropping and scaling. An additional advantage of the proposed algorithm is that the detection procedure does not require the original image.

We consider blind separation of linear mixtures of digital communication signals in noise. When little or nothing can be assumed about the mixing matrix, signal separation may be achieved by exploiting structural properties of the transmitted signals. ILSP and ILSE are two iterative least squares (ILS) separation algorithms that exploit the finite-alphabet property. ILSE is monotonically convergent and performs very well, but its complexity is exponential in the number of signals; ILSP is computationally cheaper, but is not guaranteed to converge monotonically, and leaves much to be desired in terms of BER-SNR performance relative to ILSE. We propose two computationally efficient and provably monotonically convergent ILS blind separation algorithms based on an optimal scaling Lemma. The signal estimation step of both algorithms is reminiscent of successive interference cancellation (SIC) ideas. For well-conditioned data and moderate SNR, the proposed algorithms attain the performance of ILSE at the complexity cost of ILSP.

COPERM is a novel paradigm for energy compaction and signal compression, whose foundation is a simple but powerful idea: any signal can be transformed to resemble a more desirable signal from a class of "target" signals, by means of a suitable permutation of its samples. The approach is well-suited for transform domain energy compaction prior to transform-domain compression of persistent broadband signals. The associated optimal permutation precoders are surprisingly simple, and the permutation precoding overhead can be made modest-resulting in improved overall rate-distortion performance.

A novel optimal adaptive scalar quantization method is proposed, and its performance is investigated in the context of quantization for image compression. The idea is to perform frequent and complete (non-incremental) block-optimal quantizer redesign, but under a codebook constraint which assures that the overhead required to specify the new quantizer is small. The intuition is that a few levels are usually sufficient to accurately describe a small image block, provided these are chosen optimally and independently for each block. In addition to limiting overhead, the codebook constraint can be exploited to derive an efficient dynamic programming algorithm for block-optimal quantizer design. Some experimental results and comparisons are also included.

Investigates the problem of retrieving similar shapes from a large database; in particular, we focus on medical tumor shapes (finding tumors that are similar to a given pattern). We use a natural similarity function for shape matching, based on concepts from mathematical morphology, and we show how it can be lower-bounded by a set of shape features for safely pruning candidates, thus giving fast and correct output. These features can be organized in a spatial access method, leading to fast indexing for range queries and nearest-neighbor queries. In addition to the lower-bounding, our second contribution is the design of a fast algorithm for nearest-neighbor searching, achieving significant speedup while provably guaranteeing correctness. Our experiments demonstrate that roughly 90% of the candidates can be pruned using these techniques, resulting in up to 27 times better performance compared to sequential scanning.

Morphological openings and closings can be viewed as consistent MAP estimators of smooth random binary image signals immersed in i.i.d. clutter, or suffering from i.i.d. random dropouts. We revisit this viewpoint under much more general assumptions and show that, quite surprisingly, the above interpretation is still valid.

Sidiropoulos et al. (1994) demonstrated that morphological openings and closings can be viewed as maximum a posteriori (MAP) estimators of morphologically smooth signals in signal-independent i.i.d. noise. The present authors extend these results to the M-fold independent observation case, and show that the aforementioned estimators are strongly consistent. We also demonstrate the validity of a thresholding conjecture (Sidiropoulos et al., 1994) by simulation, and use it to evaluate estimator performance. Taken together, these results can help determine the least upper bound, M , on M, which guarantees virtually error-free reconstruction of morphologically smooth images.

We have shown previously that morphological openings and closings can be viewed as consistent MAP estimators of morphologically smooth binary image signals immersed in i.i.d. union (clutter) noise, or suffering from i.i.d. random dropouts. We revisit this viewpoint under a different set of assumptions, which allows the explicit incorporation of geometric and morphological constraints into the noise model, i.e., the noise may now exhibit a geometric structure; surprisingly, it turns out that this affects neither the optimality nor the consistency of these filters.

We model digital binary image data as realizations of a uniformly bounded discrete random set (or discrete random set, for short), which is a mathematical object that can be directly defined on a finite lattice. We consider the problem of estimating realizations of discrete random sets distorted by a degradation process that can be described by a union/intersection noise model. Two distinct optimal filtering approaches are pursued. The first involves a class of "mask" filters, which arises quite naturally from the set-theoretic analysis of optimal filters. The second approach involves a class of morphological filters. We prove that under i.i.d noise morphological openings, closings, unions of openings, and intersections of closings can be viewed as MAP estimators of morphologically smooth signals. Then, we show that by using an appropriate (under a given degradation model) expansion of the optimal filter, we can obtain universal characterizations of optimality that do not rely on strong assumptions regarding the spatial interaction of geometrical primitives of the signal and the noise. The results generalize to gray-level images in a fairly straightforward manner.