AKAritra Konar

Aritra Konar

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Aritra Konar has a total of 8 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Minimizing low-rank models of high-order tensors: Hardness, span, tight relaxation, and applications

    by Nicholas D. Sidiropoulos, Paris Karakasis, Aritra Konar

    We consider the problem of finding the smallest or largest entry of a tensor of order N that is specified via its rank decomposition. Stated in a different way, we are given N sets of R-dimensional vectors and we wish to select one vector from each set such that the sum of the Hadamard product of the selected vectors is minimized or maximized. We show that this fundamental tensor problem is NP-hard for any tensor rank higher than one, and polynomial-time solvable in the rank-one case. We also propose a continuous relaxation and prove that it is tight for any rank. For low-enough ranks, the proposed continuous reformulation is amenable to low-complexity gradient-based optimization, and we propose a suite of gradient-based optimization algorithms drawing from projected gradient descent, Frank-Wolfe, or explicit parametrization of the relaxed constraints. We also show that our core results remain valid no matter what kind of polyadic tensor model is used to represent the tensor of interest, including Tucker, HOSVD/MLSVD, tensor train, or tensor ring. Next, we consider the class of problems that can be posed as special instances of the problem of interest. We show that this class includes the partition problem (and thus all NP-complete problems via polynomial-time transformation), integer least squares, integer linear programming, integer quadratic programming, sign retrieval (a special kind of mixed integer programming / restricted version of phase retrieval), and maximum likelihood decoding of parity check codes. We demonstrate promising experimental results on a number of hard problems, including state-of-art performance in decoding low density parity check codes and general parity check codes.

  • Open Access

    Minimizing Low-Rank Models of High-Order Tensors: Hardness, Span, Tight Relaxation, and Applications

    by Nicholas D. Sidiropoulos, Paris A. Karakasis, Aritra Konar

    We consider the problem of finding the smallest or largest entry of a tensor of order $N$ that is specified via its rank decomposition. Stated in a different way, we are given $N$ sets of $R$ -dimensional vectors and we wish to select one vector from each set such that the sum of the Hadamard product of the selected vectors is minimized or maximized. We show that this fundamental tensor problem is NP-hard for any tensor rank higher than one, and polynomial-time solvable in the rank-one case. We also propose a continuous relaxation and prove that it is tight for any rank. For low-enough ranks, the proposed continuous reformulation is amenable to low-complexity gradient-based optimization, and we propose a suite of gradient-based optimization algorithms drawing from projected gradient descent, Frank-Wolfe, or explicit parametrization of the relaxed constraints. We also show that our core results remain valid no matter what kind of polyadic tensor model is used to represent the tensor of interest, including Tucker, HOSVD/MLSVD, tensor train, or tensor ring. Next, we consider the class of problems that can be posed as special instances of the problem of interest. We show that this class includes the partition problem (and thus all NP-complete problems via polynomial-time transformation), integer least squares, integer linear programming, integer quadratic programming, sign retrieval (a special kind of mixed integer programming / restricted version of phase retrieval), and maximum likelihood decoding of parity check codes. We demonstrate promising experimental results on a number of hard problems, including state-of-art performance in decoding low density parity check codes and general parity check codes.


  • Cell-Edge Detection via Selective Cooperation and Generalized Canonical Correlation

    by Mohamed Salah Ibrahim, Ahmed S. Zamzam, Aritra Konar, Nicholas D. Sidiropoulos

    Improving the uplink quality of service for users located around the boundaries between cells is a key challenge in cellular systems. Existing approaches relying on power control throttle the rates of cell-center users, while multi-user detection requires accurate channel estimates for the cell-edge users, which is another challenge due to their low received signal-to-noise ratio (SNR). Utilizing the fact that cell-edge user signals are weak but common (received at roughly equal power) at different base stations (BSs), this paper establishes a connection between cell-edge user detection and generalized canonical correlation analysis (GCCA). It puts forth a GCCA-based method that leverages selective BS cooperation to recover the cell-edge user signal subspace even at low SNR. The cell-edge user signals can then be extracted from the resulting mixture via algebraic signal processing techniques. The paper includes theoretical analysis showing why GCCA recovers the correct subspace containing the cell-edge user signals under mild conditions. The proposed method can also identify the number of cell-edge users in the system, i.e., the common subspace dimension. Simulations reveal significant performance improvement relative to various multiuser detection techniques. Cell-edge detection performance is further studied as a function of how many / which BSs are selected, and it is shown that using the closest three BS is always the best choice.


  • Open Access

    Joint Graph Embedding and Alignment with Spectral Pivot

    by Paris A. Karakasis, Aritra Konar, Nicholas D. Sidiropoulos

    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.


  • Graph Matching Via the Lens of Supermodularity

    by Aritra Konar, Nicholas D. Sidiropoulos

    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.


  • Fast Algorithms for Joint Multicast Beamforming and Antenna Selection in Massive MIMO

    by Mohamed Salah Ibrahim, Aritra Konar, Nicholas D. Sidiropoulos

    Massive MIMO is currently a leading physical layer technology candidate that can dramatically enhance throughput in 5G systems, for both unicast and multicast transmission modalities. As antenna elements are becoming smaller and cheaper in the mmW range compared to radio frequency (RF) chains, it is crucial to perform antenna selection at the transmitter, such that the available RF chains are switched to an appropriate subset of antennas. This paper considers the joint problem of multicast beamforming and antenna selection for a single multicast group in massive MIMO systems. The prior state-of-art for this problem relies on semi-definite relaxation (SDR), which cannot scale up to the massive MIMO regime. A successive convex approximation (SCA) based approach is proposed to tackle max-min fair joint multicast beamforming and antenna selection. The key idea of SCA is to successively approximate the non-convex problem by a class of non-smooth, convex optimization problems. Two fast and memory efficient first-order methods are proposed to solve each SCA subproblem. Simulations demonstrate that the proposed algorithms outperform the existing state-of-art approach in terms of solution quality and run time, in both traditional and especially in massive MIMO settings.


  • Learning to Beamform for Minimum Outage

    by Yunmei Shi, Aritra Konar, Nicholas D. Sidiropoulos, Xing-Peng Mao, Yong-Tan Liu

    Acquiring channel state information (CSI) at the base station (BS) is a critical requirement for successfully employing transmit beamforming in multiantenna systems. In practice, channel estimation/quantization errors, feedback delays, and fast fading can make it difficult to obtain accurate CSI at the BS. In this paper, we consider an outage-based approach for transmit beamforming in order to deal with the channel uncertainty at the BS. Our formulation is applicable to both point-to-point transmit beamforming as well as single-group multicasting scenarios. A key difference from prior works is that we do not assume knowledge of the underlying channel distribution; instead, stochastic approximation is used for computing approximate solutions of a nonconvex stochastic optimization problem via simple first-order methods (FOMs). We evaluate the performance of our FOMs in two settings: First) where we design a beamformer at the BS based on historical channel realizations collected over a relatively long time window before deployment, and second) in a post-deployment phase where we perform incremental updates of our beamformer based on intermittent, delayed, or peer feedback. Simulation results reveal the effectiveness of FOMs for our problem compared to other alternatives.


  • A Simple and Effective Approach for Transmit Antenna Selection in Multiuser Massive MIMO Leveraging Submodularity

    by Aritra Konar, Nicholas D. Sidiropoulos

    Massive MIMO systems are expected to enable great improvements in spectral and energy efficiency. Realizing these benefits in practice, however, is hindered by the cost and complexity of implementing large-scale antenna systems. A potential solution is to use transmit antenna selection for reducing the number of radio-frequency (RF) chains at the base station. In this paper, we consider the NP-hard discrete optimization problem of performing transmit antenna selection in the downlink of a single cell, multiuser massive MIMO system by maximizing the downlink sum-rate capacity with fixed user power allocation subject to various RF switching constraints. Whereas prior work has focused on using convex relaxation based schemes, which lack theoretical performance guarantees and can be computationally demanding, we adopt a very different approach. We establish that the objective function of this antenna selection problem is monotone and satisfies an important property known as submodularity, while the RF switching constraints are expressible as the independent sets of a matroid. This implies that a simple greedy algorithm can be used to guarantee a constant-factor approximation for all problem instances. Simulations indicate that greedy selection yields a near-optimal solution in practice and captures a significant fraction of the total downlink channel capacity at substantially lower complexity relative to convex relaxation based approaches, even with very few RF chains. This paves the way for substantial reduction in hardware complexity of massive MIMO systems while using very simple algorithms.


  • First-Order Methods for Fast Feasibility Pursuit of Non-convex QCQPs

    by Aritra Konar, Nicholas D. Sidiropoulos

    Quadratically constrained quadratic programming (QCQP) is NP-hard in its general non-convex form, yet it frequently arises in various engineering applications. 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 heuristic 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 to large-scale problems. While a priori it may appear that these benefits come at the expense of technical sophistication, rendering our approach too simple to even merit consideration for a non-convex and NP-hard problem, we provide compelling empirical evidence to the contrary. Experiments on synthetic as well as real-world instances of non-convex QCQPs reveal the surprising effectiveness of first-order methods compared to more established and sophisticated alternatives.