OpenRaiser/Intern-Atlas huggingface dataset:
A Deterministic Theory for Exact Non-Convex Phase Retrieval
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we analyze the non-convex framework of Wirtinger Flow (WF) for phase retrieval and identify a novel sufficient condition for universal exact recovery through the lens of low rank matrix recovery theory. Via a perspective in the lifted domain, we show that the convergence of the WF iterates to a true solution is attained geometrically under a single condition on the lifted forward model. As a result, a deterministic relationship between the accuracy of spectral initialization and the validity of {the regularity condition} is derived. In particular, we determine that a certain concentration property on the spectral matrix must hold uniformly with a sufficiently tight constant. This culminates into a sufficient condition that is equivalent to a restricted isometry-type property over rank-1, positive semi-definite matrices, and amounts to a less stringent requirement on the lifted forward model than those of prominent low-rank-matrix-recovery methods in the literature. We characterize the performance limits of our framework in terms of the tightness of the concentration property via novel bounds on the convergence rate and on the signal-to-noise ratio such that the theoretical guarantees are valid using the spectral initialization at the proper sample complexity.
An inexact matching approach for the comparison of plane curves with general elastic metrics
Venue: arXiv cs.CG 2020
Year: 2020

This paper introduces a new mathematical formulation and numerical approach for the computation of distances and geodesics between immersed planar curves. Our approach combines the general simplifying transform for first-order elastic metrics that was recently introduced by Kurtek and Needham, together with a relaxation of the matching constraint using parametrization-invariant fidelity metrics. The main advantages of this formulation are that it leads to a simple optimization problem for discretized curves, and that it provides a flexible approach to deal with noisy, inconsistent or corrupted data. These benefits are illustrated via a few preliminary numerical results.
Self-Supervised Fast Adaptation for Denoising via Meta-Learning
Venue: arXiv cs.CV 2020
Year: 2020

Under certain statistical assumptions of noise, recent self-supervised approaches for denoising have been introduced to learn network parameters without true clean images, and these methods can restore an image by exploiting information available from the given input (i.e., internal statistics) at test time. However, self-supervised methods are not yet combined with conventional supervised denoising methods which train the denoising networks with a large number of external training samples. Thus, we propose a new denoising approach that can greatly outperform the state-of-the-art supervised denoising methods by adapting their network parameters to the given input through selfsupervision without changing the networks architectures. Moreover, we propose a meta-learning algorithm to enable quick adaptation of parameters to the specific input at test time. We demonstrate that the proposed method can be easily employed with state-of-the-art denoising networks without additional parameters, and achieve state-of-the-art performance on numerous benchmark datasets.
GRIDS: Interactive Layout Design with Integer Programming
Venue: arXiv cs.HC 2020
Year: 2020

Grid layouts are used by designers to spatially organise user interfaces when sketching and wireframing. However, their design is largely time consuming manual work. This is challenging due to combinatorial explosion and complex objectives, such as alignment, balance, and expectations regarding positions. This paper proposes a novel optimisation approach for the generation of diverse grid-based layouts. Our mixed integer linear programming (MILP) model offers a rigorous yet efficient method for grid generation that ensures packing, alignment, grouping, and preferential positioning of elements. Further, we present techniques for interactive diversification, enhancement, and completion of grid layouts (Figure 1). These capabilities are demonstrated using GRIDS1, a wireframing tool that provides designers with real-time layout suggestions. We report findings from a ratings study (N = 13) and a design study (N = 16), lending evidence for the benefit of computational grid generation during early stages of design.
Neural Network Tomography
Venue: arXiv cs.NI 2020
Year: 2020

Network tomography, a classic research problem in the realm of network monitoring, refers to the methodology of inferring unmeasured network attributes using selected end-to-end path measurements. In the research community, network tomography is generally investigated under the assumptions of known network topology, correlated path measurements, bounded number of faulty nodes/links, or even special network protocol support. The applicability of network tomography is considerably constrained by these strong assumptions, which therefore frequently position it in the theoretical world. In this regard, we revisit network tomography from the practical perspective by establishing a generic framework that does not rely on any of these assumptions or the types of performance metrics. Given only the end-to-end path performance metrics of sampled node pairs, the proposed framework, NeuTomography, utilizes deep neural network and data augmentation to predict the unmeasured performance metrics via learning non-linear relationships between node pairs and underlying unknown topological/routing properties. In addition, NeuTomography can be employed to reconstruct the original network topology, which is critical to most network planning tasks. Extensive experiments using real network data show that comparing to baseline solutions, NeuTomography can predict network characteristics and reconstruct network topologies with significantly higher accuracy and robustness using only limited measurement data.
Independent Domination in Subcubic Graphs
Venue: arXiv cs.DM 2020
Year: 2020

A set $S$ of vertices in a graph $G$ is a dominating set if every vertex not in $S$ is adjacent to a vertex in $S$. If, in addition, $S$ is an independent set, then $S$ is an independent dominating set. The independent domination number $i(G)$ of $G$ is the minimum cardinality of an independent dominating set in $G$. In 2013 Goddard and Henning [Discrete Math 313 (2013), 839--854] conjectured that if $G$ is a connected cubic graph of order $n$, then $i(G) \le \frac{3}{8}n$, except if $G$ is the complete bipartite graph $K_{3,3}$ or the $5$-prism $C_5 \, \Box \, K_2$. Further they construct two infinite families of connected cubic graphs with independent domination three-eighths their order. They remark that perhaps it is even true that for $n > 10$ these two families are only families for which equality holds. In this paper, we provide a new family of connected cubic graphs $G$ of order $n$ such that $i(G) = \frac{3}{8}n$. We also show that if $G$ is a subcubic graph of order $n$ with no isolated vertex, then $i(G) \le \frac{1}{2}n$, and we characterize the graphs achieving equality in this bound.
Understanding video streaming algorithms in the wild
Venue: arXiv cs.NI 2020
Year: 2020

While video streaming algorithms are a hot research area, with interesting new approaches proposed every few months, little is known about the behavior of the streaming algorithms deployed across large online streaming platforms that account for a substantial fraction of Internet traffic. We thus study adaptive bitrate streaming algorithms in use at 10 such video platforms with diverse target audiences. We collect traces of each video player's response to controlled variations in network bandwidth, and examine the algorithmic behavior: how risk averse is an algorithm in terms of target buffer; how long does it takes to reach a stable state after startup; how reactive is it in attempting to match bandwidth versus operating stably; how efficiently does it use the available network bandwidth; etc. We find that deployed algorithms exhibit a wide spectrum of behaviors across these axes, indicating the lack of a consensus one-size-fits-all solution. We also find evidence that most deployed algorithms are tuned towards stable behavior rather than fast adaptation to bandwidth variations, some are tuned towards a visual perception metric rather than a bitrate-based metric, and many leave a surprisingly large amount of the available bandwidth unused.
Energy Efficient Distributed Processing for IoT
Venue: arXiv cs.NI 2020
Year: 2020

In this paper, the entire IoT-fog-cloud architecture is modelled, the service placement problem is optimized through Mixed Integer Linear Programming (MILP) and the total power consumption is jointly minimized for processing and networking. Four aspects of IoT service placements are examined: 1) non-splittable services, 2) splittable services, 3) inter-service processing overhead for sub-service synchronization and 4) deployment of special-purpose cloud data centers (SP-DCs). The results showed that for a capacitated problem, service splitting introduces power consumption savings of up to 86% compared to 46% with non-splittable services in relation to processing in general-purpose data centers (GP-DCs). Moreover, it is observed that the inter sub-service processing overhead has a great influence on the total number of service splits. However much insignificant the ratio of the processing overhead, the results showed that this is not a trivial matter and hence much attention needs to paid to this area in order to make the best use of the resources that are available in the edge of the network. Moreover, the optimization results showed that, for very high demands, power savings of up to 50% could be achieved with SP-DCs compared to 30% with GP-DCs.
Spherical Image Generation from a Single Normal Field of View Image by Considering Scene Symmetry
Venue: arXiv cs.CV 2020
Year: 2020

Spherical images taken in all directions (360 degrees) allow representing the surroundings of the subject and the space itself, providing an immersive experience to the viewers. Generating a spherical image from a single normal-field-of-view (NFOV) image is convenient and considerably expands the usage scenarios because there is no need to use a specific panoramic camera or take images from multiple directions; however, it is still a challenging and unsolved problem. The primary challenge is controlling the high degree of freedom involved in generating a wide area that includes the all directions of the desired plausible spherical image. On the other hand, scene symmetry is a basic property of the global structure of the spherical images, such as rotation symmetry, plane symmetry and asymmetry. We propose a method to generate spherical image from a single NFOV image, and control the degree of freedom of the generated regions using scene symmetry. We incorporate scene-symmetry parameters as latent variables into conditional variational autoencoders, following which we learn the conditional probability of spherical images for NFOV images and scene symmetry. Furthermore, the probability density functions are represented using neural networks, and scene symmetry is implemented using both circular shift and flip of the hidden variables. Our experiments show that the proposed method can generate various plausible spherical images, controlled from symmetric to asymmetric.
Shallow Encoder Deep Decoder (SEDD) Networks for Image Encryption and Decryption
Venue: arXiv cs.LG 2020
Year: 2020

This paper explores a new framework for lossy image encryption and decryption using a simple shallow encoder neural network E for encryption, and a complex deep decoder neural network D for decryption. E is kept simple so that encoding can be done on low power and portable devices and can in principle be any nonlinear function which outputs an encoded vector. D is trained to decode the encodings using the dataset of image - encoded vector pairs obtained from E and happens independently of E. As the encodings come from E which while being a simple neural network, still has thousands of random parameters and therefore the encodings would be practically impossible to crack without D. This approach differs from autoencoders as D is trained completely independently of E, although the structure may seem similar. Therefore, this paper also explores empirically if a deep neural network can learn to reconstruct the original data in any useful form given the output of a neural network or any other nonlinear function, which can have very useful applications in Cryptanalysis. Experiments demonstrate the potential of the framework through qualitative and quantitative evaluation of the decoded images from D along with some limitations.
List Decoding for Oblivious Arbitrarily Varying MACs: Constrained and Gaussian
Venue: arXiv cs.IT 2020
Year: 2020

This paper provides upper and lower bounds on list sizes of list decoding for two-user oblivious arbitrarily varying multiple access channels (AVMACs). An oblivious AVMAC consists of two users who wish to transmit messages (without cooperation) to a remote receiver, a malicious jammer who only has access to the codebooks of both users (which are also known to every party), and a receiver who is required to decode the message pair sent by both users. The transmitters send codewords which encode messages subject to input constraints. The jammer, without knowing the transmitted codeword pair, injects adversarial noise subject to state constraints so as to actively corrupt the communication from both users to the receiver. It was left as an open question by Cai (2016) to nail down the smallest list sizes for constrained AVMACs. Our inner and outer bounds are based on a judicious notion of symmetrizability for AVMACs introduced by Cai (2016) with twists to incorporate input and state constraints. The analysis follows techniques by Csiszár and Narayan (1988). When no constraints are imposed, our bound collapse to prior results by Cai (2016) which characterized the list-decoding capacity region of unconstrained AVMACs. Techniques used in this paper can also be extended to the Gaussian case and we characterize the list-decoding capacity region for Gaussian AVMACs. The converse argument relies on a bounding technique recently used by Hosseinigoki and Kosut (2019).
Benchmarking In-Hand Manipulation
Venue: arXiv cs.RO 2020
Year: 2020

The purpose of this benchmark is to evaluate the planning and control aspects of robotic in-hand manipulation systems. The goal is to assess the system's ability to change the pose of a hand-held object by either using the fingers, environment or a combination of both. Given an object surface mesh from the YCB data-set, we provide examples of initial and goal states (i.e.\ static object poses and fingertip locations) for various in-hand manipulation tasks. We further propose metrics that measure the error in reaching the goal state from a specific initial state, which, when aggregated across all tasks, also serves as a measure of the system's in-hand manipulation capability. We provide supporting software, task examples, and evaluation results associated with the benchmark. All the supporting material is available at https://robot-learning.cs.utah.edu/project/benchmarking_in_hand_manipulation
Robust Facial Landmark Detection via Aggregation on Geometrically Manipulated Faces
Venue: arXiv cs.CV 2020
Year: 2020

In this work, we present a practical approach to the problem of facial landmark detection. The proposed method can deal with large shape and appearance variations under the rich shape deformation. To handle the shape variations we equip our method with the aggregation of manipulated face images. The proposed framework generates different manipulated faces using only one given face image. The approach utilizes the fact that small but carefully crafted geometric manipulation in the input domain can fool deep face recognition models. We propose three different approaches to generate manipulated faces in which two of them perform the manipulations via adversarial attacks and the other one uses known transformations. Aggregating the manipulated faces provides a more robust landmark detection approach which is able to capture more important deformations and variations of the face shapes. Our approach is demonstrated its superiority compared to the state-of-the-art method on benchmark datasets AFLW, 300-W, and COFW.
A Generalization of Teo and Sethuraman's Median Stable Marriage Theorem
Venue: arXiv cs.DM 2020
Year: 2020

Let $L$ be any finite distributive lattice and $B$ be any boolean predicate defined on $L$ such that the set of elements satisfying $B$ is a sublattice of $L$. Consider any subset $M$ of $L$ of size $k$ of elements of $L$ that satisfy $B$. Then, we show that $k$ generalized median elements generated from $M$ also satisfy $B$. We call this result generalized median theorem on finite distributive lattices. When this result is applied to the stable matching, we get Teo and Sethuraman's median stable matching theorem. Our proof is much simpler than that of Teo and Sethuraman. When the generalized median theorem is applied to the assignment problem, we get an analogous result for market clearing price vectors.
Assignment-based Path Choice Estimation for Metro Systems Using Smart Card Data
Venue: arXiv cs.DS 2020
Year: 2020

Urban rail services are the principal means of public transportation in many cities. To understand the crowding patterns and develop efficient operation strategies in the system, obtaining path choices is important. This paper proposed an assignment-based path choice estimation framework using automated fare collection (AFC) data. The framework captures the inherent correlation of crowding among stations, as well as the interaction between path choice and left behind. The path choice estimation is formulated as an optimization problem. The original problem is intractable because of a non-analytical constraint and a non-linear equation constraint. A solution procedure is proposed to decompose the original problem into three tractable sub-problems, which can be solved efficiently. The model is validated using both synthetic data and real-world AFC data in Hong Kong Mass Transit Railway (MTR) system. The synthetic data test validates the model's effectiveness in estimating path choice parameters, which can outperform the purely simulation-based optimization methods in both accuracy and efficiency. The test results using actual data show that the estimated path shares are more reasonable than survey-derived path shares and uniform path shares. Model robustness in terms of different initial values and different case study dates are also verified.
Optimal dynamic information provision in traffic routing
Venue: arXiv cs.GT 2020
Year: 2020

We consider a two-road dynamic routing game where the state of one of the roads (the "risky road") is stochastic and may change over time. This generates room for experimentation. A central planner may wish to induce some of the (finite number of atomic) agents to use the risky road even when the expected cost of travel there is high in order to obtain accurate information about the state of the road. Since agents are strategic, we show that in order to generate incentives for experimentation the central planner however needs to limit the number of agents using the risky road when the expected cost of travel on the risky road is low. In particular, because of congestion, too much use of the risky road when the state is favorable would make experimentation no longer incentive compatible. We characterize the optimal incentive compatible recommendation system, first in a two-stage game and then in an infinite-horizon setting. In both cases, this system induces only partial, rather than full, information sharing among the agents (otherwise there would be too much exploitation of the risky road when costs there are low).
RSL-Net: Localising in Satellite Images From a Radar on the Ground
Venue: arXiv cs.CV 2020
Year: 2020

This paper is about localising a vehicle in an overhead image using FMCW radar mounted on a ground vehicle. FMCW radar offers extraordinary promise and efficacy for vehicle localisation. It is impervious to all weather types and lighting conditions. However the complexity of the interactions between millimetre radar wave and the physical environment makes it a challenging domain. Infrastructure-free large-scale radar-based localisation is in its infancy. Typically here a map is built and suitable techniques, compatible with the nature of sensor, are brought to bear. In this work we eschew the need for a radar-based map; instead we simply use an overhead image -- a resource readily available everywhere. This paper introduces a method that not only naturally deals with the complexity of the signal type but does so in the context of cross modal processing.
Campfire: Compressible, Regularization-Free, Structured Sparse Training for Hardware Accelerators
Venue: arXiv cs.LG 2020
Year: 2020

This paper studies structured sparse training of CNNs with a gradual pruning technique that leads to fixed, sparse weight matrices after a set number of epochs. We simplify the structure of the enforced sparsity so that it reduces overhead caused by regularization. The proposed training methodology Campfire explores pruning at granularities within a convolutional kernel and filter. We study various tradeoffs with respect to pruning duration, level of sparsity, and learning rate configuration. We show that our method creates a sparse version of ResNet-50 and ResNet-50 v1.5 on full ImageNet while remaining within a negligible <1% margin of accuracy loss. To ensure that this type of sparse training does not harm the robustness of the network, we also demonstrate how the network behaves in the presence of adversarial attacks. Our results show that with 70% target sparsity, over 75% top-1 accuracy is achievable.
SMT-Friendly Formalization of the Solidity Memory Model
Venue: arXiv cs.PL 2020
Year: 2020

Solidity is the dominant programming language for Ethereum smart contracts. This paper presents a high-level formalization of the Solidity language with a focus on the memory model. The presented formalization covers all features of the language related to managing state and memory. In addition, the formalization we provide is effective: all but few features can be encoded in the quantifier-free fragment of standard SMT theories. This enables precise and efficient reasoning about the state of smart contracts written in Solidity. The formalization is implemented in the solc-verify verifier and we provide an extensive set of tests that covers the breadth of the required semantics. We also provide an evaluation on the test set that validates the semantics and shows the novelty of the approach compared to other Solidity-level contract analysis tools.