OpenRaiser/Intern-Atlas huggingface dataset:
A Framework for Private Matrix Analysis
Venue: arXiv cs.LG 2020
Year: 2020

We study private matrix analysis in the sliding window model where only the last $W$ updates to matrices are considered useful for analysis. We give first efficient $o(W)$ space differentially private algorithms for spectral approximation, principal component analysis, and linear regression. We also initiate and show efficient differentially private algorithms for two important variants of principal component analysis: sparse principal component analysis and non-negative principal component analysis. Prior to our work, no such result was known for sparse and non-negative differentially private principal component analysis even in the static data setting. These algorithms are obtained by identifying sufficient conditions on positive semidefinite matrices formed from streamed matrices. We also show a lower bound on space required to compute low-rank approximation even if the algorithm gives multiplicative approximation and incurs additive error. This follows via reduction to a certain communication complexity problem.
Universal Layout Emulation for Long-Term Database Archival
Venue: arXiv cs.DB 2020
Year: 2020

Research on alternate media technologies, like film, synthetic DNA, and glass, for long-term data archival has received a lot of attention recently due to the media obsolescence issues faced by contemporary storage media like tape, Hard Disk Drives (HDD), and Solid State Disks (SSD). While researchers have developed novel layout and encoding techniques for archiving databases on these new media types, one key question remains unaddressed: How do we ensure that the decoders developed today will be available and executable by a user who is restoring an archived database several decades later in the future, on a computing platform that potentially does not even exist today? In this paper, we make the case for Universal Layout Emulation (ULE), a new approach for future-proof, long-term database archival that advocates archiving decoders together with the data to ensure successful recovery. In order to do so, ULE brings together concepts from Data Management and Digital Preservation communities by using emulation for archiving decoders. In order to show that ULE can be implemented in practice, we present the design and evaluation of Micr'Olonys, an end-to-end long-term database archival system that can be used to archive databases using visual analog media like film, microform, and archival paper.
Improved Error Performance in NOMA-based Diamond Relaying
Venue: arXiv cs.IT 2020
Year: 2020

Non-orthogonal multiple access (NOMA)-based cooperative relaying systems (CRS) has emerged as a solution to the spectral inefficiency problem of the conventional cooperative relaying systems thanks to the NOMA integration. Thus, as a subset of NOMA-CRS, the NOMA-based diamond relaying network (NOMA-DRN) also provides a performance gain in terms of throughput. However, the NOMA-DRN has a poor error performance due to the second phase (uplink), indeed, it has a error floor regardless of the transmit power, power allocation and channel qualities. To address this problem, in this paper, we propose a novel NOMA-DRN schemes where joint maximum likelihood (JML) decoding is implemented at the destination. Then, we define the performance metrics (i.e., bit error rate (BER) and the diversity order ) of the NOMA-DRN with the JML and analyze the computational complexity. Moreover, we demonstrate that the new NOMA-DRN with JML can cope with the error floor penalty of the conventional NOMA-DRN. Hence, a spectral efficient NOMA-CRS scheme can be achieved with high data reliability. Specifically, this improvement can reach to $\sim20-30dB$ in the transmit power which is superb gain in terms of energy efficiency perspective. Furthermore, with the proposed NOMA-DRN with the JML, the full diversity order can be achieved in the low-medium SNR region.
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
Venue: arXiv cs.CC 2020
Year: 2020

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $Θ(n)$. This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM '20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
On the construction of explosive relation algebras
Venue: arXiv cs.LO 2020
Year: 2020

Fork algebras are an extension of relation algebras obtained by extending the set of logical symbols with a binary operator called fork. This class of algebras was introduced by Haeberer and Veloso in the early 90's aiming at enriching relation algebra, an already successful language for program specification, with the capability of expressing some form of parallel computation. The further study of this class of algebras led to many meaningful results linked to interesting properties of relation algebras such as representability and finite axiomatizability, among others. Also in the 90's, Veloso introduced a subclass of relation algebras that are expansible to fork algebras, admitting a large number of non-isomorphic expansions, referred to as explosive relation algebras. In this work we discuss some general techniques for constructing algebras of this type.
Discovering Reliable Causal Rules
Venue: arXiv cs.LG 2020
Year: 2020

We study the problem of deriving policies, or rules, that when enacted on a complex system, cause a desired outcome. Absent the ability to perform controlled experiments, such rules have to be inferred from past observations of the system's behaviour. This is a challenging problem for two reasons: First, observational effects are often unrepresentative of the underlying causal effect because they are skewed by the presence of confounding factors. Second, naive empirical estimations of a rule's effect have a high variance, and, hence, their maximisation can lead to random results. To address these issues, first we measure the causal effect of a rule from observational data---adjusting for the effect of potential confounders. Importantly, we provide a graphical criteria under which causal rule discovery is possible. Moreover, to discover reliable causal rules from a sample, we propose a conservative and consistent estimator of the causal effect, and derive an efficient and exact algorithm that maximises the estimator. On synthetic data, the proposed estimator converges faster to the ground truth than the naive estimator and recovers relevant causal rules even at small sample sizes. Extensive experiments on a variety of real-world datasets show that the proposed algorithm is efficient and discovers meaningful rules.
An FPGA Accelerated Method for Training Feed-forward Neural Networks Using Alternating Direction Method of Multipliers and LSMR
Venue: arXiv cs.LG 2020
Year: 2020

In this project, we have successfully designed, implemented, deployed and tested a novel FPGA accelerated algorithm for neural network training. The algorithm itself was developed in an independent study option. This training method is based on Alternating Direction Method of Multipliers algorithm, which has strong parallel characteristics and avoids procedures such as matrix inversion that are problematic in hardware designs by employing LSMR. As an intermediate stage, we fully implemented the ADMM-LSMR method in C language for feed-forward neural networks with a flexible number of layers and hidden size. We demonstrated that the method can operate with fixed-point arithmetic without compromising the accuracy. Next, we devised an FPGA accelerated version of the algorithm using Intel FPGA SDK for OpenCL and performed extensive optimisation stages followed by successful deployment of the program on an Intel Arria 10 GX FPGA. The FPGA accelerated program showed up to 6 times speed up comparing to equivalent CPU implementation while achieving promising accuracy.
Duluth at SemEval-2020 Task 7: Using Surprise as a Key to Unlock Humorous Headlines
Venue: arXiv cs.CL 2020
Year: 2020

We use pretrained transformer-based language models in SemEval-2020 Task 7: Assessing the Funniness of Edited News Headlines. Inspired by the incongruity theory of humor, we use a contrastive approach to capture the surprise in the edited headlines. In the official evaluation, our system gets 0.531 RMSE in Subtask 1, 11th among 49 submissions. In Subtask 2, our system gets 0.632 accuracy, 9th among 32 submissions.
Reconfigurable Intelligent Surfaces for Localization: Position and Orientation Error Bounds
Venue: arXiv cs.IT 2020
Year: 2020

Next-generation cellular networks will witness the creation of smart radio environments (SREs), where walls and objects can be coated with reconfigurable intelligent surfaces (RISs) to strengthen the communication and localization coverage by controlling the reflected multipath. In fact, RISs have been recently introduced not only to overcome communication blockages due to obstacles but also for high-precision localization of mobile users in GPS denied environments, e.g., indoors. Towards this vision, this paper presents the localization performance limits for communication scenarios where a single next-generation NodeB base station (gNB), equipped with multiple-antennas, infers the position and the orientation of the user equipment(UE) in a RIS-assisted SRE. We consider a signal model that is valid also for near-field propagation conditions, as the usually adopted far-field assumption does not always hold, especially for large RISs. For the considered scenario, we derive the Cramer-Rao lower bound (CRLB) for assessing the ultimate localization and orientation performance of synchronous and asynchronous signaling schemes. In addition, we propose a closed-form RIS phase profile that well suits joint communication and localization. We perform extensive numerical results to assess the performance of our scheme for various localization scenarios and RIS phase design. Numerical results show that the proposed scheme can achieve remarkable performance, even in asynchronous signaling and that the proposed phase design approaches the numerical optimal phase design that minimizes the CRLB.
MFL_COVID19: Quantifying Country-based Factors affecting Case Fatality Rate in Early Phase of COVID-19 Epidemic via Regularised Multi-task Feature Learning
Venue: arXiv cs.CV 2020
Year: 2020

Recent outbreak of COVID-19 has led a rapid global spread around the world. Many countries have implemented timely intensive suppression to minimize the infections, but resulted in high case fatality rate (CFR) due to critical demand of health resources. Other country-based factors such as sociocultural issues, ageing population etc., has also influenced practical effectiveness of taking interventions to improve morality in early phase. To better understand the relationship of these factors across different countries with COVID-19 CFR is of primary importance to prepare for potentially second wave of COVID-19 infections. In the paper, we propose a novel regularized multi-task learning based factor analysis approach for quantifying country-based factors affecting CFR in early phase of COVID-19 epidemic. We formulate the prediction of CFR progression as a ML regression problem with observed CFR and other countries-based factors. In this formulation, all CFR related factors were categorized into 6 sectors with 27 indicators. We proposed a hybrid feature selection method combining filter, wrapper and tree-based models to calibrate initial factors for a preliminary feature interaction. Then we adopted two typical single task model (Ridge and Lasso regression) and one state-of-the-art MTFL method (fused sparse group lasso) in our formulation. The fused sparse group Lasso (FSGL) method allows the simultaneous selection of a common set of country-based factors for multiple time points of COVID-19 epidemic and also enables incorporating temporal smoothness of each factor over the whole early phase period. Finally, we proposed one novel temporal voting feature selection scheme to balance the weight instability of multiple factors in our MTFL model.
Multiple Private Key Generation for Continuous Memoryless Sources with A Helper
Venue: arXiv cs.IT 2020
Year: 2020

We propose a method to study the secrecy constraints in key generation problems where side information might be present at untrusted users. Our method is inspired by a recent work of Hayashi and Tan who used the Rényi divergence as the secrecy measure to study the output statistics of applying hash functions to a random sequence. By generalizing the achievability result of Hayashi and Tan to the multi-terminal case, we obtain the output statistics of applying hash functions to multiple random sequences, which turn out to be an important tool in the achievability proof of strong secrecy capacity regions of key generation problems with side information at untrusted users. To illustrate the power of our method, we derive the capacity region of the multiple private key generation problem with an untrusted helper for continuous memoryless sources under Markov conditions. The converse proof of our result follows by generalizing a result of Nitinawarat and Narayan to the case with side information at untrusted users.
Dynamically Computing Adversarial Perturbations for Recurrent Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Convolutional and recurrent neural networks have been widely employed to achieve state-of-the-art performance on classification tasks. However, it has also been noted that these networks can be manipulated adversarially with relative ease, by carefully crafted additive perturbations to the input. Though several experimentally established prior works exist on crafting and defending against attacks, it is also desirable to have theoretical guarantees on the existence of adversarial examples and robustness margins of the network to such examples. We provide both in this paper. We focus specifically on recurrent architectures and draw inspiration from dynamical systems theory to naturally cast this as a control problem, allowing us to dynamically compute adversarial perturbations at each timestep of the input sequence, thus resembling a feedback controller. Illustrative examples are provided to supplement the theoretical discussions.
Crowding Prediction of In-Situ Metro Passengers Using Smart Card Data
Venue: arXiv cs.LG 2020
Year: 2020

The metro system is playing an increasingly important role in the urban public transit network, transferring a massive human flow across space everyday in the city. In recent years, extensive research studies have been conducted to improve the service quality of metro systems. Among them, crowd management has been a critical issue for both public transport agencies and train operators. In this paper, by utilizing accumulated smart card data, we propose a statistical model to predict in-situ passenger density, i.e., number of on-board passengers between any two neighbouring stations, inside a closed metro system. The proposed model performs two main tasks: i) forecasting time-dependent Origin-Destination (OD) matrix by applying mature statistical models; and ii) estimating the travel time cost required by different parts of the metro network via truncated normal mixture distributions with Expectation-Maximization (EM) algorithm. Based on the prediction results, we are able to provide accurate prediction of in-situ passenger density for a future time point. A case study using real smart card data in Singapore Mass Rapid Transit (MRT) system demonstrate the efficacy and efficiency of our proposed method.
Detecting Informal Organization Through Data Mining Techniques
Venue: arXiv cs.CY 2020
Year: 2020

One of the main topics in human resources management is the subject of informal organizations in the organization such that recognizing and managing such informal organizations play an important role in the organizations. Some managers are trying to recognize the relations between informal organizations and being a member of them by which they could assist the formal organization development. Methods of recognizing informal organizations are complicated and occasionally even impossible. This study aims to provide a method for recognizing such organizations using data mining techniques. This study classifies indices of human resources influencing the creation of informal organizations, including individual, social, and work characteristics of an organizations employees. Then, a questionnaire was designed and distributed among employees. A database was created from obtained data. Applied data mining techniques in this study are factor analysis, clustering by K-means, classification by decision trees, and finally association rule mining by GRI algorithm. At the end, a model is presented that is applicable for recognizing the similar characteristics between people for optimal recognition of informal organizations and usage of this information.
Back to the Future: Revisiting Mouse and Keyboard Interaction for HMD-based Immersive Analytics
Venue: arXiv cs.HC 2020
Year: 2020

With the rise of natural user interfaces, immersive analytics applications often focus on novel forms of interaction modalities such as mid-air gestures, gaze or tangible interaction utilizing input devices such as depth-sensors, touch screens and eye-trackers. At the same time, traditional input devices such as the physical keyboard and mouse are used to a lesser extent. We argue, that for certain work scenarios, such as conducting analytic tasks at stationary desktop settings, it can be valuable to combine the benefits of novel and established input devices as well as input modalities to create productive immersive analytics environments.
Towards a Practical Virtual Office for Mobile Knowledge Workers
Venue: arXiv cs.HC 2020
Year: 2020

As more people work from home or during travel, new opportunities and challenges arise around mobile office work. On one hand, people may work at flexible hours, independent of traffic limitations, but on the other hand, they may need to work at makeshift spaces, with less than optimal working conditions and decoupled from co-workers. Virtual Reality (VR) has the potential to change the way information workers work: it enables personal bespoke working environments even on the go and allows new collaboration approaches that can help mitigate the effects of physical distance. In this paper, we investigate opportunities and challenges for realizing a mobile VR offices environments and discuss implications from recent findings of mixing standard off-the-shelf equipment, such as tablets, laptops or desktops, with VR to enable effective, efficient, ergonomic, and rewarding mobile knowledge work. Further, we investigate the role of conceptual and physical spaces in a mobile VR office.
Efficient Projection Algorithms onto the Weighted l1 Ball
Venue: arXiv cs.LG 2020
Year: 2020

Projected gradient descent has been proved efficient in many optimization and machine learning problems. The weighted $\ell_1$ ball has been shown effective in sparse system identification and features selection. In this paper we propose three new efficient algorithms for projecting any vector of finite length onto the weighted $\ell_1$ ball. The first two algorithms have a linear worst case complexity. The third one has a highly competitive performances in practice but the worst case has a quadratic complexity. These new algorithms are efficient tools for machine learning methods based on projected gradient descent such as compress sensing, feature selection. We illustrate this effectiveness by adapting an efficient compress sensing algorithm to weighted projections. We demonstrate the efficiency of our new algorithms on benchmarks using very large vectors. For instance, it requires only 8 ms, on an Intel I7 3rd generation, for projecting vectors of size $10^7$.
Centralized & Distributed Deep Reinforcement Learning Methods for Downlink Sum-Rate Optimization
Venue: arXiv cs.IT 2020
Year: 2020

For a multi-cell, multi-user, cellular network downlink sum-rate maximization through power allocation is a nonconvex and NP-hard optimization problem. In this paper, we present an effective approach to solving this problem through single- and multi-agent actor-critic deep reinforcement learning (DRL). Specifically, we use finite-horizon trust region optimization. Through extensive simulations, we show that we can simultaneously achieve higher spectral efficiency than state-of-the-art optimization algorithms like weighted minimum mean-squared error (WMMSE) and fractional programming (FP), while offering execution times more than two orders of magnitude faster than these approaches. Additionally, the proposed trust region methods demonstrate superior performance and convergence properties than the Advantage Actor-Critic (A2C) DRL algorithm. In contrast to prior approaches, the proposed decentralized DRL approaches allow for distributed optimization with limited CSI and controllable information exchange between BSs while offering competitive performance and reduced training times.
Nonlinear Spectral Geometry Processing via the TV Transform
Venue: arXiv cs.GR 2020
Year: 2020

We introduce a novel computational framework for digital geometry processing, based upon the derivation of a nonlinear operator associated to the total variation functional. Such operator admits a generalized notion of spectral decomposition, yielding a sparse multiscale representation akin to Laplacian-based methods, while at the same time avoiding undesirable over-smoothing effects typical of such techniques. Our approach entails accurate, detail-preserving decomposition and manipulation of 3D shape geometry while taking an especially intuitive form: non-local semantic details are well separated into different bands, which can then be filtered and re-synthesized with a straightforward linear step. Our computational framework is flexible, can be applied to a variety of signals, and is easily adapted to different geometry representations, including triangle meshes and point clouds. We showcase our method throughout multiple applications in graphics, ranging from surface and signal denoising to detail transfer and cubic stylization.