We introduce and study coordinate-wise powers of subvarieties of
$\mathbb{P}^n$, i.e. varieties arising from raising all points in a given
subvariety of $\mathbb{P}^n$ to the $r$-th power, coordinate by coordinate.
This corresponds to studying the image of a subvariety of $\mathbb{P}^n$ under
the quotient of $\mathbb{P}^n$ by the action of the finite group
$\mathbb{Z}_r^{n+1}$. We determine the degree of coordinate-wise powers and
study their defining equations, particularly for hypersurfaces and linear
spaces. Applying these results, we compute the degree of the variety of
orthostochastic matrices and determine iterated dual and reciprocal varieties
of power sum hypersurfaces. We also establish a link between coordinate-wise
squares of linear spaces and the study of real symmetric matrices with a
degenerate eigenspectrum.
Authors' comments: 26 pages
A probability distribution over {-1, 1}^n is (eps, k)-wise uniform if,
roughly, it is eps-close to the uniform distribution when restricted to any k
coordinates. We consider the problem of how far an (eps, k)-wise uniform
distribution can be from any globally k-wise uniform distribution. We show that
every (eps, k)-wise uniform distribution is O(n^(k/2) eps)-close to a k-wise
uniform distribution in total variation distance. In addition, we show that
this bound is optimal for all even k: we find an (eps, k)-wise uniform
distribution that is Omega(n^(k/2) eps)-far from any k-wise uniform
distribution in total variation distance. For k = 1, we get a better upper
bound of O(eps), which is also optimal.
One application of our closeness result is to the sample complexity of
testing whether a distribution is k-wise uniform or delta-far from k-wise
uniform. We give an upper bound of O(n^k/delta^2) (or O(log n/delta^2) when k =
1) on the required samples. We show an improved upper bound of
O~(n^(k/2)/delta^2) for the special case of testing fully uniform vs. delta-far
from k-wise uniform. Finally, we complement this with a matching lower bound of
Omega(n/delta^2) when k = 2.
Our results improve upon the best known bounds from [AAK+07], and have
simpler proofs.
Handling object interaction is a fundamental challenge in practical
multi-object tracking, even for simple interactive effects such as one object
temporarily occluding another. We formalize the problem of occlusion in
tracking with two different abstractions. In object-wise occlusion, objects
that are occluded by other objects do not generate measurements. In
measurement-wise occlusion, a previously unstudied approach, all objects may
generate measurements but some measurements may be occluded by others. While
the relative validity of each abstraction depends on the situation and sensor,
measurement-wise occlusion fits into probabilistic multi-object tracking
algorithms with much looser assumptions on object interaction. Its value is
demonstrated by showing that it naturally derives a popular approximation for
lidar tracking, and by an example of visual tracking in image space.
Authors' comments: presenting at 21st International Conference on Information Fusion,
2018
Recommender systems can mitigate the information overload problem by
suggesting users' personalized items. In real-world recommendations such as
e-commerce, a typical interaction between the system and its users is -- users
are recommended a page of items and provide feedback; and then the system
recommends a new page of items. To effectively capture such interaction for
recommendations, we need to solve two key problems -- (1) how to update
recommending strategy according to user's \textit{real-time feedback}, and 2)
how to generate a page of items with proper display, which pose tremendous
challenges to traditional recommender systems. In this paper, we study the
problem of page-wise recommendations aiming to address aforementioned two
challenges simultaneously. In particular, we propose a principled approach to
jointly generate a set of complementary items and the corresponding strategy to
display them in a 2-D page; and propose a novel page-wise recommendation
framework based on deep reinforcement learning, DeepPage, which can optimize a
page of items with proper display based on real-time feedback from users. The
experimental results based on a real-world e-commerce dataset demonstrate the
effectiveness of the proposed framework.
Authors' comments: arXiv admin note: text overlap with arXiv:1802.06501
The Gaia mission has detected a large number of active galactic nuclei (AGN)
and galaxies, but these objects must be identified among the 1000-fold more
numerous stars. Extant astrometric AGN catalogs do not have the uniform sky
coverage required to detect and characterize the all-sky low-multipole proper
motion signals produced by the barycenter motion, gravitational waves, and
cosmological effects. To remedy this, we present an all-sky sample of 567,721
AGN in Gaia Data Release 1, selected using WISE two-color criteria. The catalog
has fairly uniform sky coverage beyond the Galactic plane, with a mean density
of 12.8 AGN per square degree. The objects have magnitudes ranging from $G=8.8$
down to Gaia's magnitude limit, $G=20.7$. The catalog is approximately 50%
complete but suffers from low stellar contamination, roughly 0.2%. We predict
that the end-of-mission Gaia proper motions for this catalog will enable
detection of the secular aberration drift to high significance (23$\sigma$) and
will limit the anisotropy of the Hubble expansion to about 2%.
Authors' comments: 11 pages, 7 figures; Submitted to ApJS
Superiorization reduces, not necessarily minimizes, the value of a target
function while seeking constraints-compatibility. This is done by taking a
solely feasibility-seeking algorithm, analyzing its perturbations resilience,
and proactively perturbing its iterates accordingly to steer them toward a
feasible point with reduced value of the target function. When the perturbation
steps are computationally efficient, this enables generation of a superior
result with essentially the same computational cost as that of the original
feasibility-seeking algorithm. In this work, we refine previous formulations of
the superiorization method to create a more general framework, enabling target
function reduction steps that do not require partial derivatives of the target
function. In perturbations that use partial derivatives the step-sizes in the
perturbation phase of the superiorization method are chosen independently from
the choice of the nonascent directions. This is no longer true when
component-wise perturbations are employed. In that case, the step-sizes must be
linked to the choice of the nonascent direction in every step. Besides
presenting and validating these notions, we give a computational demonstration
of superiorization with component-wise perturbations for a problem of
computerized tomography image reconstruction.
Authors' comments: Numerical Algorithms, accepted for publication
Recommender systems play a crucial role in mitigating the problem of
information overload by suggesting users' personalized items or services. The
vast majority of traditional recommender systems consider the recommendation
procedure as a static process and make recommendations following a fixed
strategy. In this paper, we propose a novel recommender system with the
capability of continuously improving its strategies during the interactions
with users. We model the sequential interactions between users and a
recommender system as a Markov Decision Process (MDP) and leverage
Reinforcement Learning (RL) to automatically learn the optimal strategies via
recommending trial-and-error items and receiving reinforcements of these items
from users' feedbacks. In particular, we introduce an online user-agent
interacting environment simulator, which can pre-train and evaluate model
parameters offline before applying the model online. Moreover, we validate the
importance of list-wise recommendations during the interactions between users
and agent, and develop a novel approach to incorporate them into the proposed
framework LIRD for list-wide recommendations. The experimental results based on
a real-world e-commerce dataset demonstrate the effectiveness of the proposed
framework.
Ellis and the third author showed, verifying a conjecture of Frankl, that any
$3$-wise intersecting family of subsets of $\{1,2,\dots,n\}$ admitting a
transitive automorphism group has cardinality $o(2^n)$, while a construction of
Frankl demonstrates that the same conclusion need not hold under the weaker
constraint of being regular. Answering a question of Cameron, Frankl and Kantor
from 1989, we show that the restriction of admitting a transitive automorphism
group may be relaxed significantly: we prove that any $3$-wise intersecting
family of subsets of $\{1,2,\dots,n\}$ that is regular and increasing has
cardinality $o(2^n)$.
There is a critical need to develop new educational technology applications
that analyze the data collected by universities to ensure that students
graduate in a timely fashion (4 to 6 years); and they are well prepared for
jobs in their respective fields of study. In this paper, we present a novel
approach for analyzing historical educational records from a large, public
university to perform next-term grade prediction; i.e., to estimate the grades
that a student will get in a course that he/she will enroll in the next term.
Accurate next-term grade prediction holds the promise for better student degree
planning, personalized advising and automated interventions to ensure that
students stay on track in their chosen degree program and graduate on time. We
present a factorization-based approach called Matrix Factorization with
Temporal Course-wise Influence that incorporates course-wise influence effects
and temporal effects for grade prediction. In this model, students and courses
are represented in a latent "knowledge" space. The grade of a student on a
course is modeled as the similarity of their latent representation in the
"knowledge" space. Course-wise influence is considered as an additional factor
in the grade prediction. Our experimental results show that the proposed method
outperforms several baseline approaches and infer meaningful patterns between
pairs of courses within academic programs.
Authors' comments: 8 pages, 5 figures
How to effectively approximate real-valued parameters with binary codes plays
a central role in neural network binarization. In this work, we reveal an
important fact that binarizing different layers has a widely-varied effect on
the compression ratio of network and the loss of performance. Based on this
fact, we propose a novel and flexible neural network binarization method by
introducing the concept of layer-wise priority which binarizes parameters in
inverse order of their layer depth. In each training step, our method selects a
specific network layer, minimizes the discrepancy between the original
real-valued weights and its binary approximations, and fine-tunes the whole
network accordingly. During the iteration of the above process, it is
significant that we can flexibly decide whether to binarize the remaining
floating layers or not and explore a trade-off between the loss of performance
and the compression ratio of model. The resulting binary network is applied for
efficient pedestrian detection. Extensive experimental results on several
benchmarks show that under the same compression ratio, our method achieves much
lower miss rate and faster detection speed than the state-of-the-art neural
network binarization method.
Authors' comments: More experiments on image classification are planned
Convolutional neural networks have gained a remarkable success in computer
vision. However, most usable network architectures are hand-crafted and usually
require expertise and elaborate design. In this paper, we provide a block-wise
network generation pipeline called BlockQNN which automatically builds
high-performance networks using the Q-Learning paradigm with epsilon-greedy
exploration strategy. The optimal network block is constructed by the learning
agent which is trained sequentially to choose component layers. We stack the
block to construct the whole auto-generated network. To accelerate the
generation process, we also propose a distributed asynchronous framework and an
early stop strategy. The block-wise generation brings unique advantages: (1) it
performs competitive results in comparison to the hand-crafted state-of-the-art
networks on image classification, additionally, the best network generated by
BlockQNN achieves 3.54% top-1 error rate on CIFAR-10 which beats all existing
auto-generate networks. (2) in the meanwhile, it offers tremendous reduction of
the search space in designing networks which only spends 3 days with 32 GPUs,
and (3) moreover, it has strong generalizability that the network built on
CIFAR also performs well on a larger-scale ImageNet dataset.
Authors' comments: Accepted to CVPR 2018
In this paper, we propose an end-to-end group-wise deep co-saliency detection
approach to address the co-salient object discovery problem based on the fully
convolutional network (FCN) with group input and group output. The proposed
approach captures the group-wise interaction information for group images by
learning a semantics-aware image representation based on a convolutional neural
network, which adaptively learns the group-wise features for co-saliency
detection. Furthermore, the proposed approach discovers the collaborative and
interactive relationships between group-wise feature representation and
single-image individual feature representation, and model this in a
collaborative learning framework. Finally, we set up a unified end-to-end deep
learning scheme to jointly optimize the process of group-wise feature
representation learning and the collaborative learning, leading to more
reliable and robust co-saliency detection results. Experimental results
demonstrate the effectiveness of our approach in comparison with the
state-of-the-art approaches.
Authors' comments: IJCAI 2017
We develop and analyze efficient "coordinate-wise" methods for finding the
leading eigenvector, where each step involves only a vector-vector product. We
establish global convergence with overall runtime guarantees that are at least
as good as Lanczos's method and dominate it for slowly decaying spectrum. Our
methods are based on combining a shift-and-invert approach with coordinate-wise
algorithms for linear regression.
Variational autoencoders (VAEs), that are built upon deep neural networks
have emerged as popular generative models in computer vision. Most of the work
towards improving variational autoencoders has focused mainly on making the
approximations to the posterior flexible and accurate, leading to tremendous
progress. However, there have been limited efforts to replace pixel-wise
reconstruction, which have known shortcomings. In this work, we use real-valued
non-volume preserving transformations (real NVP) to exactly compute the
conditional likelihood of the data given the latent distribution. We show that
a simple VAE with this form of reconstruction is competitive with complicated
VAE structures, on image modeling tasks. As part of our model, we develop
powerful conditional coupling layers that enable real NVP to learn with fewer
intermediate layers.
A family of sets is said to be symmetric if its automorphism group is
transitive, and $3$-wise intersecting if any three sets in the family have
nonempty intersection. Frankl conjectured in 1981 that if $\mathcal{A}$ is a
symmetric $3$-wise intersecting family of subsets of $\{1,2,\dots,n\}$, then
$|\mathcal{A}| = o(2^n)$. Here, we give a short proof of Frankl's conjecture
using a 'sharp threshold' result of Friedgut and Kalai.
Authors' comments: 7 pages, typo corrected in description of 'tree' construction in
Section 3. Proc. Amer. Math. Soc
Cluster-wise linear regression (CLR), a clustering problem intertwined with
regression, is to find clusters of entities such that the overall sum of
squared errors from regressions performed over these clusters is minimized,
where each cluster may have different variances. We generalize the CLR problem
by allowing each entity to have more than one observation, and refer to it as
generalized CLR. We propose an exact mathematical programming based approach
relying on column generation, a column generation based heuristic algorithm
that clusters predefined groups of entities, a metaheuristic genetic algorithm
with adapted Lloyd's algorithm for K-means clustering, a two-stage approach,
and a modified algorithm of Sp{\"a}th \cite{Spath1979} for solving generalized
CLR. We examine the performance of our algorithms on a stock keeping unit (SKU)
clustering problem employed in forecasting halo and cannibalization effects in
promotions using real-world retail data from a large supermarket chain. In the
SKU clustering problem, the retailer needs to cluster SKUs based on their
seasonal effects in response to promotions. The seasonal effects are the
results of regressions with predictors being promotion mechanisms and seasonal
dummies performed over clusters generated. We compare the performance of all
proposed algorithms for the SKU problem with real-world and synthetic data.
A Finsler space $(M,F)$ is called flag-wise positively curved, if for any
$x\in M$ and any tangent plane $\mathbf{P}\subset T_xM$, we can find a nonzero
vector $y\in \mathbf{P}$, such that the flag curvature $K^F(x,y,
\mathbf{P})>0$. Though compact positively curved spaces are very rare in both
Riemannian and Finsler geometry, flag-wise positively curved metrics should be
easy to be found. A generic Finslerian perturbation for a non-negatively curved
homogeneous metric may have a big chance to produce flag-wise positively curved
metrics. This observation leads our discovery of these metrics on many compact
manifolds. First we prove any Lie group $G$ such that its Lie algebra
$\mathfrak{g}$ is compact non-Abelian and $\dim\mathfrak{c}(\mathfrak{g})\leq
1$ admits flag-wise positively curved left invariant Finsler metrics. Similar
techniques can be applied to our exploration for more general compact coset
spaces. We will prove, whenever $G/H$ is a compact simply connected coset
space, $G/H$ and $S^1\times G/H$ admit flag-wise positively curved Finsler
metrics. This provides abundant examples for this type of metrics, which are
not homogeneous in general.
Authors' comments: 9 pages. In the newest version, Theorem 1.3 is strenghened to provide
many more examples
In software testing, the large size of the input domain makes exhaustively
testing the inputs a daunting and often impossible task. Pair-wise testing is a
popular approach to combinatorial testing problems. This paper reviews
Pair-wise testing and its history, strengths, weaknesses, and tools for
generating test cases.
(Abridged) We aim at measuring the near-infrared photometry, and deriving the
mass, age, temperature, and surface gravity of WISE J085510.74-071442.5
(J0855-0714), which is the coolest known object beyond the Solar System as of
today. We use publicly available data from the archives of the HST and the VLT
to determine the emission of this source at 1.153 micron (F110W) and 1.575
micron (CH_4). J0855-0714 is detected at both wavelengths with signal-to-noise
ratio of ~10 (F110W) and ~4 (CH_4-off) at the peak of the corresponding PSFs.
This is the first detection of J0855-0714 in the H-band. We measure 26.31 +/-
0.10 and 23.22 +/- 0.35 mag in F110W and CH_4 (Vega system). J0855-0714 remains
unresolved in the HST images that have a spatial resolution of 0.22".
Companions at separations of 0.5 AU (similar brightness) and at ~1 AU (~1 mag
fainter in the F110W filter) are discarded. By combining the new data with
published photometry, we build the spectral energy distribution of J0855-0714
from 0.89 to 22.09 micron, and contrast it against state-of-the-art
solar-metallicity models of planetary atmospheres. We determine a temperature
of 225-250 K, a bolometric luminosity of log L/Lsol = -8.57, and a high surface
gravity of log g = 5.0 (cm/s2), which suggests an old age although such a high
gravity is not fully compatible with evolutionary models. After comparison with
the cooling theory for brown dwarfs and planets, we infer a mass in the
interval 2-10 Mjup for ages of 1-12 Gyr and log g > 3.5 (cm/s2). At the age of
the Sun, J0855-0714 would be a ~5-Mjup free-floating planetary-mass object.
J0855-0714 may represent the old image of the free-floating planetary-mass
objects of similar mass discovered in star-forming regions and young stellar
clusters. As many J0855-0714-like objects as M5-L2 stars may be expected to
populate the solar neighborhood.
Authors' comments: Accepted for publication in A&A
The WISE satellite has detected hundreds of millions sources over the entire
sky. Classifying them reliably is however a challenging task due to
degeneracies in WISE multicolour space and low levels of detection in its two
longest-wavelength bandpasses. Here we aim at obtaining comprehensive and
reliable star, galaxy and quasar catalogues based on automatic source
classification in full-sky WISE data. This means that the final classification
will employ only parameters available from WISE itself, in particular those
reliably measured for a majority of sources. For the automatic classification
we applied the support vector machines (SVM) algorithm, which requires a
training sample with relevant classes already identified, and we chose to use
the SDSS spectroscopic dataset for that purpose. By calibrating the classifier
on the test data drawn from SDSS, we first established that a polynomial kernel
is preferred over a radial one for this particular dataset. Next, using three
classification parameters (W1 magnitude, W1-W2 colour, and a differential
aperture magnitude) we obtained very good classification efficiency in all the
tests. At the bright end, the completeness for stars and galaxies reaches ~95%,
deteriorating to ~80% at W1=16 mag, while for quasars it stays at a level of
~95% independently of magnitude. Similar numbers are obtained for purity.
Application of the classifier to full-sky WISE data, flux-limited to 16 mag
(Vega) in the 3.4 {\mu}m channel, and appropriate a posteriori cleaning allowed
us to obtain reliably-looking catalogues of star and galaxy candidates.
However, the sources flagged by the classifier as `quasars' are in fact
dominated by dusty galaxies but also exhibit contamination from sources located
mainly at low ecliptic latitudes, consistent with Solar System objects.
[abridged]
Authors' comments: 18 pages, 17 figures, 4 tables
