July 27, 2019

2870 words 14 mins read

Paper Group ANR 708

A Well-Tempered Landscape for Non-convex Robust Subspace Recovery. Zeroth Order Nonconvex Multi-Agent Optimization over Networks. DeepPermNet: Visual Permutation Learning. Direction-aware Spatial Context Features for Shadow Detection. Learning a Unified Control Policy for Safe Falling. A+D Net: Training a Shadow Detector with Adversarial Shadow Att …

A Well-Tempered Landscape for Non-convex Robust Subspace Recovery


Title	A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
Authors	Tyler Maunu, Teng Zhang, Gilad Lerman
Abstract	We present a mathematical analysis of a non-convex energy landscape for robust subspace recovery. We prove that an underlying subspace is the only stationary point and local minimizer in a specified neighborhood under a deterministic condition on a dataset. If the deterministic condition is satisfied, we further show that a geodesic gradient descent method over the Grassmannian manifold can exactly recover the underlying subspace when the method is properly initialized. Proper initialization by principal component analysis is guaranteed with a simple deterministic condition. Under slightly stronger assumptions, the gradient descent method with a piecewise constant step-size scheme achieves linear convergence. The practicality of the deterministic condition is demonstrated on some statistical models of data, and the method achieves almost state-of-the-art recovery guarantees on the Haystack Model for different regimes of sample size and ambient dimension. In particular, when the ambient dimension is fixed and the sample size is large enough, we show that our gradient method can exactly recover the underlying subspace for any fixed fraction of outliers (less than 1).
Tasks
Published	2017-06-13
URL	http://arxiv.org/abs/1706.03896v3
PDF	http://arxiv.org/pdf/1706.03896v3.pdf
PWC	https://paperswithcode.com/paper/a-well-tempered-landscape-for-non-convex
Repo
Framework

Zeroth Order Nonconvex Multi-Agent Optimization over Networks


Title	Zeroth Order Nonconvex Multi-Agent Optimization over Networks
Authors	Davood Hajinezhad, Mingyi Hong, Alfredo Garcia
Abstract	In this paper, we consider distributed optimization problems over a multi-agent network, where each agent can only partially evaluate the objective function, and it is allowed to exchange messages with its immediate neighbors. Differently from all existing works on distributed optimization, our focus is given to optimizing a class of non-convex problems, and under the challenging setting where each agent can only access the zeroth-order information (i.e., the functional values) of its local functions. For different types of network topologies such as undirected connected networks or star networks, we develop efficient distributed algorithms and rigorously analyze their convergence and rate of convergence (to the set of stationary solutions). Numerical results are provided to demonstrate the efficiency of the proposed algorithms.
Tasks	Distributed Optimization
Published	2017-10-27
URL	http://arxiv.org/abs/1710.09997v3
PDF	http://arxiv.org/pdf/1710.09997v3.pdf
PWC	https://paperswithcode.com/paper/zeroth-order-nonconvex-multi-agent
Repo
Framework

DeepPermNet: Visual Permutation Learning


Title	DeepPermNet: Visual Permutation Learning
Authors	Rodrigo Santa Cruz, Basura Fernando, Anoop Cherian, Stephen Gould
Abstract	We present a principled approach to uncover the structure of visual data by solving a novel deep learning task coined visual permutation learning. The goal of this task is to find the permutation that recovers the structure of data from shuffled versions of it. In the case of natural images, this task boils down to recovering the original image from patches shuffled by an unknown permutation matrix. Unfortunately, permutation matrices are discrete, thereby posing difficulties for gradient-based methods. To this end, we resort to a continuous approximation of these matrices using doubly-stochastic matrices which we generate from standard CNN predictions using Sinkhorn iterations. Unrolling these iterations in a Sinkhorn network layer, we propose DeepPermNet, an end-to-end CNN model for this task. The utility of DeepPermNet is demonstrated on two challenging computer vision problems, namely, (i) relative attributes learning and (ii) self-supervised representation learning. Our results show state-of-the-art performance on the Public Figures and OSR benchmarks for (i) and on the classification and segmentation tasks on the PASCAL VOC dataset for (ii).
Tasks	Representation Learning
Published	2017-04-10
URL	http://arxiv.org/abs/1704.02729v1
PDF	http://arxiv.org/pdf/1704.02729v1.pdf
PWC	https://paperswithcode.com/paper/deeppermnet-visual-permutation-learning
Repo
Framework

Direction-aware Spatial Context Features for Shadow Detection


Title	Direction-aware Spatial Context Features for Shadow Detection
Authors	Xiaowei Hu, Lei Zhu, Chi-Wing Fu, Jing Qin, Pheng-Ann Heng
Abstract	Shadow detection is a fundamental and challenging task, since it requires an understanding of global image semantics and there are various backgrounds around shadows. This paper presents a novel network for shadow detection by analyzing image context in a direction-aware manner. To achieve this, we first formulate the direction-aware attention mechanism in a spatial recurrent neural network (RNN) by introducing attention weights when aggregating spatial context features in the RNN. By learning these weights through training, we can recover direction-aware spatial context (DSC) for detecting shadows. This design is developed into the DSC module and embedded in a CNN to learn DSC features at different levels. Moreover, a weighted cross entropy loss is designed to make the training more effective. We employ two common shadow detection benchmark datasets and perform various experiments to evaluate our network. Experimental results show that our network outperforms state-of-the-art methods and achieves 97% accuracy and 38% reduction on balance error rate.
Tasks	Detecting Shadows, Shadow Detection
Published	2017-12-12
URL	http://arxiv.org/abs/1712.04142v2
PDF	http://arxiv.org/pdf/1712.04142v2.pdf
PWC	https://paperswithcode.com/paper/direction-aware-spatial-context-features-for
Repo
Framework

Learning a Unified Control Policy for Safe Falling


Title	Learning a Unified Control Policy for Safe Falling
Authors	Visak CV Kumar, Sehoon Ha, C Karen Liu
Abstract	Being able to fall safely is a necessary motor skill for humanoids performing highly dynamic tasks, such as running and jumping. We propose a new method to learn a policy that minimizes the maximal impulse during the fall. The optimization solves for both a discrete contact planning problem and a continuous optimal control problem. Once trained, the policy can compute the optimal next contacting body part (e.g. left foot, right foot, or hands), contact location and timing, and the required joint actuation. We represent the policy as a mixture of actor-critic neural network, which consists of n control policies and the corresponding value functions. Each pair of actor-critic is associated with one of the n possible contacting body parts. During execution, the policy corresponding to the highest value function will be executed while the associated body part will be the next contact with the ground. With this mixture of actor-critic architecture, the discrete contact sequence planning is solved through the selection of the best critics while the continuous control problem is solved by the optimization of actors. We show that our policy can achieve comparable, sometimes even higher, rewards than a recursive search of the action space using dynamic programming, while enjoying 50 to 400 times of speed gain during online execution.
Tasks	Continuous Control
Published	2017-03-08
URL	http://arxiv.org/abs/1703.02905v2
PDF	http://arxiv.org/pdf/1703.02905v2.pdf
PWC	https://paperswithcode.com/paper/learning-a-unified-control-policy-for-safe
Repo
Framework

A+D Net: Training a Shadow Detector with Adversarial Shadow Attenuation


Title	A+D Net: Training a Shadow Detector with Adversarial Shadow Attenuation
Authors	Hieu Le, Tomas F. Yago Vicente, Vu Nguyen, Minh Hoai, Dimitris Samaras
Abstract	We propose a novel GAN-based framework for detecting shadows in images, in which a shadow detection network (D-Net) is trained together with a shadow attenuation network (A-Net) that generates adversarial training examples. The A-Net modifies the original training images constrained by a simplified physical shadow model and is focused on fooling the D-Net’s shadow predictions. Hence, it is effectively augmenting the training data for D-Net with hard-to-predict cases. The D-Net is trained to predict shadows in both original images and generated images from the A-Net. Our experimental results show that the additional training data from A-Net significantly improves the shadow detection accuracy of D-Net. Our method outperforms the state-of-the-art methods on the most challenging shadow detection benchmark (SBU) and also obtains state-of-the-art results on a cross-dataset task, testing on UCF. Furthermore, the proposed method achieves accurate real-time shadow detection at 45 frames per second.
Tasks	Detecting Shadows, Shadow Detection
Published	2017-12-04
URL	http://arxiv.org/abs/1712.01361v2
PDF	http://arxiv.org/pdf/1712.01361v2.pdf
PWC	https://paperswithcode.com/paper/ad-net-training-a-shadow-detector-with
Repo
Framework

Robust Wirtinger Flow for Phase Retrieval with Arbitrary Corruption


Title	Robust Wirtinger Flow for Phase Retrieval with Arbitrary Corruption
Authors	Jinghui Chen, Lingxiao Wang, Xiao Zhang, Quanquan Gu
Abstract	We consider the robust phase retrieval problem of recovering the unknown signal from the magnitude-only measurements, where the measurements can be contaminated by both sparse arbitrary corruption and bounded random noise. We propose a new nonconvex algorithm for robust phase retrieval, namely Robust Wirtinger Flow to jointly estimate the unknown signal and the sparse corruption. We show that our proposed algorithm is guaranteed to converge linearly to the unknown true signal up to a minimax optimal statistical precision in such a challenging setting. Compared with existing robust phase retrieval methods, we achieve an optimal sample complexity of $O(n)$ in both noisy and noise-free settings. Thorough experiments on both synthetic and real datasets corroborate our theory.
Tasks
Published	2017-04-20
URL	http://arxiv.org/abs/1704.06256v2
PDF	http://arxiv.org/pdf/1704.06256v2.pdf
PWC	https://paperswithcode.com/paper/robust-wirtinger-flow-for-phase-retrieval
Repo
Framework

Maximizing the information learned from finite data selects a simple model


Title	Maximizing the information learned from finite data selects a simple model
Authors	Henry H. Mattingly, Mark K. Transtrum, Michael C. Abbott, Benjamin B. Machta
Abstract	We use the language of uninformative Bayesian prior choice to study the selection of appropriately simple effective models. We advocate for the prior which maximizes the mutual information between parameters and predictions, learning as much as possible from limited data. When many parameters are poorly constrained by the available data, we find that this prior puts weight only on boundaries of the parameter manifold. Thus it selects a lower-dimensional effective theory in a principled way, ignoring irrelevant parameter directions. In the limit where there is sufficient data to tightly constrain any number of parameters, this reduces to Jeffreys prior. But we argue that this limit is pathological when applied to the hyper-ribbon parameter manifolds generic in science, because it leads to dramatic dependence on effects invisible to experiment.
Tasks
Published	2017-05-02
URL	http://arxiv.org/abs/1705.01166v3
PDF	http://arxiv.org/pdf/1705.01166v3.pdf
PWC	https://paperswithcode.com/paper/maximizing-the-information-learned-from
Repo
Framework

Graph sketching-based Space-efficient Data Clustering


Title	Graph sketching-based Space-efficient Data Clustering
Authors	Anne Morvan, Krzysztof Choromanski, Cédric Gouy-Pailler, Jamal Atif
Abstract	In this paper, we address the problem of recovering arbitrary-shaped data clusters from datasets while facing \emph{high space constraints}, as this is for instance the case in many real-world applications when analysis algorithms are directly deployed on resources-limited mobile devices collecting the data. We present DBMSTClu a new space-efficient density-based \emph{non-parametric} method working on a Minimum Spanning Tree (MST) recovered from a limited number of linear measurements i.e. a \emph{sketched} version of the dissimilarity graph $\mathcal{G}$ between the $N$ objects to cluster. Unlike $k$-means, $k$-medians or $k$-medoids algorithms, it does not fail at distinguishing clusters with particular forms thanks to the property of the MST for expressing the underlying structure of a graph. No input parameter is needed contrarily to DBSCAN or the Spectral Clustering method. An approximate MST is retrieved by following the dynamic \emph{semi-streaming} model in handling the dissimilarity graph $\mathcal{G}$ as a stream of edge weight updates which is sketched in one pass over the data into a compact structure requiring $O(N \operatorname{polylog}(N))$ space, far better than the theoretical memory cost $O(N^2)$ of $\mathcal{G}$. The recovered approximate MST $\mathcal{T}$ as input, DBMSTClu then successfully detects the right number of nonconvex clusters by performing relevant cuts on $\mathcal{T}$ in a time linear in $N$. We provide theoretical guarantees on the quality of the clustering partition and also demonstrate its advantage over the existing state-of-the-art on several datasets.
Tasks
Published	2017-03-07
URL	http://arxiv.org/abs/1703.02375v5
PDF	http://arxiv.org/pdf/1703.02375v5.pdf
PWC	https://paperswithcode.com/paper/graph-sketching-based-space-efficient-data
Repo
Framework

An Efficient Algebraic Solution to the Perspective-Three-Point Problem


Title	An Efficient Algebraic Solution to the Perspective-Three-Point Problem
Authors	Tong Ke, Stergios Roumeliotis
Abstract	In this work, we present an algebraic solution to the classical perspective-3-point (P3P) problem for determining the position and attitude of a camera from observations of three known reference points. In contrast to previous approaches, we first directly determine the camera’s attitude by employing the corresponding geometric constraints to formulate a system of trigonometric equations. This is then efficiently solved, following an algebraic approach, to determine the unknown rotation matrix and subsequently the camera’s position. As compared to recent alternatives, our method avoids computing unnecessary (and potentially numerically unstable) intermediate results, and thus achieves higher numerical accuracy and robustness at a lower computational cost. These benefits are validated through extensive Monte-Carlo simulations for both nominal and close-to-singular geometric configurations.
Tasks
Published	2017-01-28
URL	http://arxiv.org/abs/1701.08237v1
PDF	http://arxiv.org/pdf/1701.08237v1.pdf
PWC	https://paperswithcode.com/paper/an-efficient-algebraic-solution-to-the
Repo
Framework

Global Weisfeiler-Lehman Graph Kernels


Title	Global Weisfeiler-Lehman Graph Kernels
Authors	Christopher Morris, Kristian Kersting, Petra Mutzel
Abstract	Most state-of-the-art graph kernels only take local graph properties into account, i.e., the kernel is computed with regard to properties of the neighborhood of vertices or other small substructures. On the other hand, kernels that do take global graph propertiesinto account may not scale well to large graph databases. Here we propose to start exploring the space between local and global graph kernels, striking the balance between both worlds. Specifically, we introduce a novel graph kernel based on the $k$-dimensional Weisfeiler-Lehman algorithm. Unfortunately, the $k$-dimensional Weisfeiler-Lehman algorithm scales exponentially in $k$. Consequently, we devise a stochastic version of the kernel with provable approximation guarantees using conditional Rademacher averages. On bounded-degree graphs, it can even be computed in constant time. We support our theoretical results with experiments on several graph classification benchmarks, showing that our kernels often outperform the state-of-the-art in terms of classification accuracies.
Tasks	Graph Classification
Published	2017-03-07
URL	http://arxiv.org/abs/1703.02379v3
PDF	http://arxiv.org/pdf/1703.02379v3.pdf
PWC	https://paperswithcode.com/paper/global-weisfeiler-lehman-graph-kernels
Repo
Framework

Block-Matching Convolutional Neural Network for Image Denoising


Title	Block-Matching Convolutional Neural Network for Image Denoising
Authors	Byeongyong Ahn, Nam Ik Cho
Abstract	There are two main streams in up-to-date image denoising algorithms: non-local self similarity (NSS) prior based methods and convolutional neural network (CNN) based methods. The NSS based methods are favorable on images with regular and repetitive patterns while the CNN based methods perform better on irregular structures. In this paper, we propose a block-matching convolutional neural network (BMCNN) method that combines NSS prior and CNN. Initially, similar local patches in the input image are integrated into a 3D block. In order to prevent the noise from messing up the block matching, we first apply an existing denoising algorithm on the noisy image. The denoised image is employed as a pilot signal for the block matching, and then denoising function for the block is learned by a CNN structure. Experimental results show that the proposed BMCNN algorithm achieves state-of-the-art performance. In detail, BMCNN can restore both repetitive and irregular structures.
Tasks	Denoising, Image Denoising
Published	2017-04-03
URL	http://arxiv.org/abs/1704.00524v1
PDF	http://arxiv.org/pdf/1704.00524v1.pdf
PWC	https://paperswithcode.com/paper/block-matching-convolutional-neural-network
Repo
Framework

YouTube-8M Video Understanding Challenge Approach and Applications


Title	YouTube-8M Video Understanding Challenge Approach and Applications
Authors	Edward Chen
Abstract	This paper introduces the YouTube-8M Video Understanding Challenge hosted as a Kaggle competition and also describes my approach to experimenting with various models. For each of my experiments, I provide the score result as well as possible improvements to be made. Towards the end of the paper, I discuss the various ensemble learning techniques that I applied on the dataset which significantly boosted my overall competition score. At last, I discuss the exciting future of video understanding research and also the many applications that such research could significantly improve.
Tasks	Video Understanding
Published	2017-06-26
URL	http://arxiv.org/abs/1706.08222v1
PDF	http://arxiv.org/pdf/1706.08222v1.pdf
PWC	https://paperswithcode.com/paper/youtube-8m-video-understanding-challenge
Repo
Framework

Learning Vector Autoregressive Models with Latent Processes


Title	Learning Vector Autoregressive Models with Latent Processes
Authors	Saber Salehkaleybar, Jalal Etesami, Negar Kiyavash, Kun Zhang
Abstract	We study the problem of learning the support of transition matrix between random processes in a Vector Autoregressive (VAR) model from samples when a subset of the processes are latent. It is well known that ignoring the effect of the latent processes may lead to very different estimates of the influences among observed processes, and we are concerned with identifying the influences among the observed processes, those between the latent ones, and those from the latent to the observed ones. We show that the support of transition matrix among the observed processes and lengths of all latent paths between any two observed processes can be identified successfully under some conditions on the VAR model. From the lengths of latent paths, we reconstruct the latent subgraph (representing the influences among the latent processes) with a minimum number of variables uniquely if its topology is a directed tree. Furthermore, we propose an algorithm that finds all possible minimal latent graphs under some conditions on the lengths of latent paths. Our results apply to both non-Gaussian and Gaussian cases, and experimental results on various synthetic and real-world datasets validate our theoretical results.
Tasks
Published	2017-02-27
URL	http://arxiv.org/abs/1702.08575v3
PDF	http://arxiv.org/pdf/1702.08575v3.pdf
PWC	https://paperswithcode.com/paper/learning-vector-autoregressive-models-with
Repo
Framework

Efficient Correlated Topic Modeling with Topic Embedding


Title	Efficient Correlated Topic Modeling with Topic Embedding
Authors	Junxian He, Zhiting Hu, Taylor Berg-Kirkpatrick, Ying Huang, Eric P. Xing
Abstract	Correlated topic modeling has been limited to small model and problem sizes due to their high computational cost and poor scaling. In this paper, we propose a new model which learns compact topic embeddings and captures topic correlations through the closeness between the topic vectors. Our method enables efficient inference in the low-dimensional embedding space, reducing previous cubic or quadratic time complexity to linear w.r.t the topic size. We further speedup variational inference with a fast sampler to exploit sparsity of topic occurrence. Extensive experiments show that our approach is capable of handling model and data scales which are several orders of magnitude larger than existing correlation results, without sacrificing modeling quality by providing competitive or superior performance in document classification and retrieval.
Tasks	Document Classification
Published	2017-07-01
URL	http://arxiv.org/abs/1707.00206v1
PDF	http://arxiv.org/pdf/1707.00206v1.pdf
PWC	https://paperswithcode.com/paper/efficient-correlated-topic-modeling-with
Repo
Framework