OpenRaiser/Intern-Atlas huggingface dataset:
Intelligent Reflecting Surface Aided Multi-User Communication: Capacity Region and Deployment Strategy
Venue: arXiv cs.IT 2021
Year: 2021

Intelligent reflecting surface (IRS) is a new promising technology that is able to reconfigure the wireless propagation channel via smart and passive signal reflection. In this paper, we investigate the capacity region of a two-user communication network with one access point (AP) aided by $M$ IRS elements for enhancing the user-AP channels, where the IRS incurs negligible delay, thus the user-AP channels via the IRS follow the classic discrete memoryless channel model. In particular, we consider two practical IRS deployment strategies that lead to different effective channels between the users and AP, namely, the distributed deployment where the $M$ elements form two IRSs, each deployed in the vicinity of one user, versus the centralized deployment where all the $M$ elements are deployed in the vicinity of the AP. First, we consider the uplink multiple-access channel (MAC) and derive the capacity/achievable rate regions for both deployment strategies under different multiple access schemes. It is shown that the centralized deployment generally outperforms the distributed deployment under symmetric channel setups in terms of achievable user rates. Next, we extend the results to the downlink broadcast channel (BC) by leveraging the celebrated uplink-downlink (or MAC-BC) duality framework, and show that the superior rate performance of centralized over distributed deployment also holds. Numerical results are presented that validate our analysis, and reveal new and useful insights for optimal IRS deployment in wireless networks.
A Lower Bound on Determinantal Complexity
Venue: arXiv cs.CC 2021
Year: 2021

The determinantal complexity of a polynomial $P \in \mathbb{F}[x_1, \ldots, x_n]$ over a field $\mathbb{F}$ is the dimension of the smallest matrix $M$ whose entries are affine functions in $\mathbb{F}[x_1, \ldots, x_n]$ such that $P = Det(M)$. We prove that the determinantal complexity of the polynomial $\sum_{i = 1}^n x_i^n$ is at least $1.5n - 3$. For every $n$-variate polynomial of degree $d$, the determinantal complexity is trivially at least $d$, and it is a long standing open problem to prove a lower bound which is super linear in $\max\{n,d\}$. Our result is the first lower bound for any explicit polynomial which is bigger by a constant factor than $\max\{n,d\}$, and improves upon the prior best bound of $n + 1$, proved by Alper, Bogart and Velasco [ABV17] for the same polynomial.
Trimmed Spline Surfaces with Accurate Boundary Control
Venue: arXiv cs.GR 2021
Year: 2021

We introduce trimmed NURBS surfaces with accurate boundary control, briefly called ABC-surfaces, as a solution to the notorious problem of constructing watertight or smooth ($G^1$ and $G^2)$ multi-patch surfaces within the function range of standard CAD/CAM systems and the associated file exchange formats. Our construction is based on the appropriate blend of a base surface, which traces out the intended global shape, and a series of reparametrized ribbons, which dominate the shape near the boundary.
Performance Analysis and User Association Optimization for Wireless Network Aided by Multiple Intelligent Reflecting Surfaces
Venue: arXiv cs.IT 2021
Year: 2021

Intelligent reflecting surface (IRS) is deemed as a promising solution to improve the spectral and energy efficiency of wireless communications cost-effectively. In this paper, we consider a wireless network where multiple base stations (BSs) serve their respective users with the aid of distributed IRSs in the downlink communication. Specifically, each IRS assists in the transmission from its associated BS to user via passive beamforming, while in the meantime, it also randomly scatters the signals from other co-channel BSs, thus resulting in additional signal as well as interference paths in the network. As such, a new IRS-user/BS association problem arises pertaining to optimally balance the passive beamforming gains from all IRSs among different BS-user communication links. To address this new problem, we first derive a tractable lower bound of the average signal-to-interference-plus-noise ratio (SINR) at the receiver of each user, termed average-signal-to-average-interference-plus-noise ratio (ASAINR), based on which two ASAINR balancing problems are formulated to maximize the minimum ASAINR among all users by optimizing the IRS-user associations without and with BS transmit power control, respectively. We also characterize the scaling behavior of user ASAINRs with the increasing number of IRS reflecting elements to investigate the different effects of IRS-reflected signal versus interference power. Moreover, to solve the two ASAINR balancing problems that are both non-convex optimization problems, we propose an optimal solution to the problem without BS power control and low-complexity suboptimal solutions to both problems by applying the branch-and-bound method and exploiting new properties of the IRS-user associations, respectively. Numerical results verify our performance analysis and also demonstrate significant performance gains of the proposed solutions over benchmark schemes.
Learning from Multiple Datasets with Heterogeneous and Partial Labels for Universal Lesion Detection in CT
Venue: arXiv cs.CV 2021
Year: 2021

Large-scale datasets with high-quality labels are desired for training accurate deep learning models. However, due to the annotation cost, datasets in medical imaging are often either partially-labeled or small. For example, DeepLesion is such a large-scale CT image dataset with lesions of various types, but it also has many unlabeled lesions (missing annotations). When training a lesion detector on a partially-labeled dataset, the missing annotations will generate incorrect negative signals and degrade the performance. Besides DeepLesion, there are several small single-type datasets, such as LUNA for lung nodules and LiTS for liver tumors. These datasets have heterogeneous label scopes, i.e., different lesion types are labeled in different datasets with other types ignored. In this work, we aim to develop a universal lesion detection algorithm to detect a variety of lesions. The problem of heterogeneous and partial labels is tackled. First, we build a simple yet effective lesion detection framework named Lesion ENSemble (LENS). LENS can efficiently learn from multiple heterogeneous lesion datasets in a multi-task fashion and leverage their synergy by proposal fusion. Next, we propose strategies to mine missing annotations from partially-labeled datasets by exploiting clinical prior knowledge and cross-dataset knowledge transfer. Finally, we train our framework on four public lesion datasets and evaluate it on 800 manually-labeled sub-volumes in DeepLesion. Our method brings a relative improvement of 49% compared to the current state-of-the-art approach in the metric of average sensitivity. We have publicly released our manual 3D annotations of DeepLesion in https://github.com/viggin/DeepLesion_manual_test_set.
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
Venue: arXiv cs.DS 2021
Year: 2021

Let $G = (V,E,w)$ be a weighted, digraph subject to a sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given a fixed source $s$ and the goal is to maintain a data structure that can answer path-queries $s \rightarrowtail v$ for any $v \in V$. In the more general single-source shortest paths (SSSP) problem the goal is to return an approximate shortest path to $v$, and in the SCC problem the goal is to maintain strongly connected components of $G$ and to answer path queries within each component. All of these problems have been very actively studied over the past two decades, but all the fast algorithms are randomized and, more significantly, they can only answer path queries if they assume a weaker model: they assume an oblivious adversary which is not adaptive and must fix the update sequence in advance. This assumption significantly limits the use of these data structures, most notably preventing them from being used as subroutines in static algorithms. All the above problems are notoriously difficult in the adaptive setting. In fact, the state-of-the-art is still the Even and Shiloach tree, which dates back all the way to 1981 and achieves total update time $O(mn)$. We present the first algorithms to break through this barrier: 1) deterministic decremental SSR/SCC with total update time $mn^{2/3 + o(1)}$ 2) deterministic decremental SSSP with total update time $n^{2+2/3+o(1)}$. To achieve these results, we develop two general techniques of broader interest for working with dynamic graphs: 1) a generalization of expander-based tools to dynamic directed graphs, and 2) a technique that we call congestion balancing and which provides a new method for maintaining flow under adversarial deletions. Using the second technique, we provide the first near-optimal algorithm for decremental bipartite matching.
Deep Ensemble of Weighted Viterbi Decoders for Tail-Biting Convolutional Codes
Venue: arXiv cs.IT 2021
Year: 2021

Tail-biting convolutional codes extend the classical zero-termination convolutional codes: Both encoding schemes force the equality of start and end states, but under the tail-biting each state is a valid termination. This paper proposes a machine-learning approach to improve the state-of-the-art decoding of tail-biting codes, focusing on the widely employed short length regime as in the LTE standard. This standard also includes a CRC code. First, we parameterize the circular Viterbi algorithm, a baseline decoder that exploits the circular nature of the underlying trellis. An ensemble combines multiple such weighted decoders, each decoder specializes in decoding words from a specific region of the channel words' distribution. A region corresponds to a subset of termination states; the ensemble covers the entire states space. A non-learnable gating satisfies two goals: it filters easily decoded words and mitigates the overhead of executing multiple weighted decoders. The CRC criterion is employed to choose only a subset of experts for decoding purpose. Our method achieves FER improvement of up to 0.75dB over the CVA in the waterfall region for multiple code lengths, adding negligible computational complexity compared to the circular Viterbi algorithm in high SNRs.
Online Disease Self-diagnosis with Inductive Heterogeneous Graph Convolutional Networks
Venue: arXiv cs.LG 2021
Year: 2021

We propose a Healthcare Graph Convolutional Network (HealGCN) to offer disease self-diagnosis service for online users based on Electronic Healthcare Records (EHRs). Two main challenges are focused in this paper for online disease diagnosis: (1) serving cold-start users via graph convolutional networks and (2) handling scarce clinical description via a symptom retrieval system. To this end, we first organize the EHR data into a heterogeneous graph that is capable of modeling complex interactions among users, symptoms and diseases, and tailor the graph representation learning towards disease diagnosis with an inductive learning paradigm. Then, we build a disease self-diagnosis system with a corresponding EHR Graph-based Symptom Retrieval System (GraphRet) that can search and provide a list of relevant alternative symptoms by tracing the predefined meta-paths. GraphRet helps enrich the seed symptom set through the EHR graph when confronting users with scarce descriptions, hence yield better diagnosis accuracy. At last, we validate the superiority of our model on a large-scale EHR dataset.
A Vision of Self-Evolving Network Management for Future Intelligent Vertical HetNet
Venue: arXiv cs.NI 2021
Year: 2021

Future integrated terrestrial-aerial-satellite networks will have to exhibit some unprecedented characteristics for the provision of both communications and computation services, and security for a tremendous number of devices with very broad and demanding requirements across multiple networks, operators, and ecosystems. Although 3GPP introduced the concept of self-organization networks (SONs) in 4G and 5G documents to automate network management, even this progressive concept will face several challenges as it may not be sufficiently agile in coping with the immense levels of complexity, heterogeneity, and mobility in the envisioned beyond-5G integrated networks. In the presented vision, we discuss how future integrated networks can be intelligently and autonomously managed to efficiently utilize resources, reduce operational costs, and achieve the targeted Quality of Experience (QoE). We introduce the novel concept of "self-evolving networks (SENs)" framework, which utilizes artificial intelligence, enabled by machine learning (ML) algorithms, to make future integrated networks fully automated and intelligently evolve with respect to the provision, adaptation, optimization, and management aspects of networking, communications, computation, and infrastructure nodes' mobility. To envisage the concept of SEN in future integrated networks, we use the Intelligent Vertical Heterogeneous Network (I-VHetNet) architecture as our reference. The paper discusses five prominent scenarios where SEN plays the main role in providing automated network management. Numerical results provide an insight on how the SEN framework improves the performance of future integrated networks. The paper presents the leading enablers and examines the challenges associated with the application of SEN concept in future integrated networks.
Ambiguity Hierarchy of Regular Infinite Tree Languages
Venue: arXiv cs.LO 2021
Year: 2021

An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is k-ambiguous (for k > 0) if for every input it has at most k accepting computations. An automaton is boundedly ambiguous if it is k-ambiguous for some $k \in \mathbb{N}$. An automaton is finitely (respectively, countably) ambiguous if for every input it has at most finitely (respectively, countably) many accepting computations. The degree of ambiguity of a regular language is defined in a natural way. A language is k-ambiguous (respectively, boundedly, finitely, countably ambiguous) if it is accepted by a k-ambiguous (respectively, boundedly, finitely, countably ambiguous) automaton. Over finite words every regular language is accepted by a deterministic automaton. Over finite trees every regular language is accepted by an unambiguous automaton. Over $ω$-words every regular language is accepted by an unambiguous Büchi automaton and by a deterministic parity automaton. Over infinite trees Carayol et al. showed that there are ambiguous languages. We show that over infinite trees there is a hierarchy of degrees of ambiguity: For every k > 1 there are k-ambiguous languages that are not k - 1 ambiguous; and there are finitely (respectively countably, uncountably) ambiguous languages that are not boundedly (respectively finitely, countably) ambiguous.
A Fast Parametric Ellipse Algorithm
Venue: arXiv cs.GR 2021
Year: 2021

This paper describes a 2-D graphics algorithm that uses shifts and adds to precisely plot a series of points on an ellipse of any shape and orientation. The algorithm can also plot an elliptic arc that starts and ends at arbitrary angles. The ellipse algorithm described here is largely based on earlier papers by Van Aken and Simar [1,2], which extend Marvin Minsky's well-known circle algorithm [3,4,5] to ellipses, and show how to cancel out the sources of error in Minsky's original algorithm. A new flatness test is presented for automatically controlling the spacing between points plotted on an ellipse or elliptic arc. Most of the calculations performed by the ellipse algorithm and flatness test use fixed-point addition and shift operations, and thus are well-suited to run on less-powerful processors. C++ source code listings are included. Keywords: parametric ellipse algorithm, rotated ellipse, Minsky circle algorithm, flatness, elliptic arc, conjugate diameters, affine invariance
Joint Beam Training and Positioning For Intelligent Reflecting Surfaces Assisted Millimeter Wave Communications
Venue: arXiv cs.IT 2021
Year: 2021

Intelligent reflecting surface (IRS) offers a cost effective solution to link blockage problem in mmWave communications, and the prerequisite of which is the accurate estimation of (1) the optimal beams for base station/access point (BS/AP) and mobile terminal (MT), (2) the optimal reflection patterns for IRSs, and (3) link blockage. In this paper, we carry out beam training design for IRSs assisted mmWave communications to estimate the aforementioned parameters. To acquire the optimal beams and reflection patterns, we firstly perform random beamforming and maximum likelihood estimation to estimate angle of arrival (AoA) and angle of departure (AoD) of the line of sight (LoS) path between BS/AP (or IRSs) and MT. Then, with the estimate of AoAs and AoDs, we propose an iterative positioning algorithm that achieves centimeter-level positioning accuracy. The obtained location information is not only a fringe benefit but also enables us to cross verify and enhance the estimation of AoA and AoD, and facilitates the prediction of blockage indicator. Numerical results show the superiority of our proposed beam training scheme and verify the performance gain brought by location information.
A Self-Supervised Gait Encoding Approach with Locality-Awareness for 3D Skeleton Based Person Re-Identification
Venue: arXiv cs.CV 2021
Year: 2021

Person re-identification (Re-ID) via gait features within 3D skeleton sequences is a newly-emerging topic with several advantages. Existing solutions either rely on hand-crafted descriptors or supervised gait representation learning. This paper proposes a self-supervised gait encoding approach that can leverage unlabeled skeleton data to learn gait representations for person Re-ID. Specifically, we first create self-supervision by learning to reconstruct unlabeled skeleton sequences reversely, which involves richer high-level semantics to obtain better gait representations. Other pretext tasks are also explored to further improve self-supervised learning. Second, inspired by the fact that motion's continuity endows adjacent skeletons in one skeleton sequence and temporally consecutive skeleton sequences with higher correlations (referred as locality in 3D skeleton data), we propose a locality-aware attention mechanism and a locality-aware contrastive learning scheme, which aim to preserve locality-awareness on intra-sequence level and inter-sequence level respectively during self-supervised learning. Last, with context vectors learned by our locality-aware attention mechanism and contrastive learning scheme, a novel feature named Constrastive Attention-based Gait Encodings (CAGEs) is designed to represent gait effectively. Empirical evaluations show that our approach significantly outperforms skeleton-based counterparts by 15-40% Rank-1 accuracy, and it even achieves superior performance to numerous multi-modal methods with extra RGB or depth information. Our codes are available at https://github.com/Kali-Hac/Locality-Awareness-SGE.
6G for Bridging the Digital Divide: Wireless Connectivity to Remote Areas
Venue: arXiv cs.NI 2021
Year: 2021

In telecommunications, network service accessibility as a requirement is closely related to equitably serving the population residing at locations that can most appropriately be described as remote. Remote connectivity, however, would have benefited from a more inclusive consideration in the existing generations of mobile communications. To remedy this, sustainability and its social impact are being positioned as key drivers of sixth generation's (6G) research and standardization activities. In particular, there has been a conscious attempt to understand the demands of remote wireless connectivity, which has led to a better understanding of the challenges that lie ahead. In this perspective, this article overviews the key challenges associated with constraints on network design and deployment to be addressed for providing broadband connectivity to rural areas, and proposes novel approaches and solutions for bridging the digital divide in those regions.
Social Analytics of Team Interaction using Dynamic Complexity Heat Maps and Network Visualizations
Venue: arXiv cs.SI 2021
Year: 2021

Given the increasing complexity of many sociotechnical work domains, effective teamwork has become increasingly crucial. While there is evidence that face-to-face communication contributes to effective teamwork, methods for understanding the time-varying nature and structure of team communication are limited. In this work, we combine sensor-based social analytics of Sociometric badges (Rhythm Badge) with two visualization techniques (Dynamic Complexity Heat Maps and Network Visualizations) to advance an intuitive way of understanding the dynamics of team interaction. To demonstrate the utility of our approach, we provide a case study that examines one team's interaction for a Lost at Sea simulation. We were able to recover transitions in the task and team interaction as well as uncover structural changes in team member energy and engagement, which we visualize using networks. Taken together, this work represents an important first step at optimizing team effectiveness by identifying critical transitions/events in team communication and interaction patterns.
How Good is your Explanation? Algorithmic Stability Measures to Assess the Quality of Explanations for Deep Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

A plethora of methods have been proposed to explain how deep neural networks reach their decisions but comparatively, little effort has been made to ensure that the explanations produced by these methods are objectively relevant. While several desirable properties for trustworthy explanations have been formulated, objective measures have been harder to derive. Here, we propose two new measures to evaluate explanations borrowed from the field of algorithmic stability: mean generalizability MeGe and relative consistency ReCo. We conduct extensive experiments on different network architectures, common explainability methods, and several image datasets to demonstrate the benefits of the proposed measures.In comparison to ours, popular fidelity measures are not sufficient to guarantee trustworthy explanations.Finally, we found that 1-Lipschitz networks produce explanations with higher MeGe and ReCo than common neural networks while reaching similar accuracy. This suggests that 1-Lipschitz networks are a relevant direction towards predictors that are more explainable and trustworthy.
Pay Attention when Required
Venue: arXiv cs.LG 2021
Year: 2021

Transformer-based models consist of interleaved feed-forward blocks - that capture content meaning, and relatively more expensive self-attention blocks - that capture context meaning. In this paper, we explored trade-offs and ordering of the blocks to improve upon the current Transformer architecture and proposed PAR Transformer. It needs 35% lower compute time than Transformer-XL achieved by replacing ~63% of the self-attention blocks with feed-forward blocks, and retains the perplexity on WikiText-103 language modelling benchmark. We further validated our results on text8 and enwiki8 datasets, as well as on the BERT model.