date Dynamic Face Video Segmentation via Reinforcement Learning. (arXiv:1907.01296v3 [cs.CV] UPDATED) By arxiv.org Published On :: For real-time semantic video segmentation, most recent works utilised a dynamic framework with a key scheduler to make online key/non-key decisions. Some works used a fixed key scheduling policy, while others proposed adaptive key scheduling methods based on heuristic strategies, both of which may lead to suboptimal global performance. To overcome this limitation, we model the online key decision process in dynamic video segmentation as a deep reinforcement learning problem and learn an efficient and effective scheduling policy from expert information about decision history and from the process of maximising global return. Moreover, we study the application of dynamic video segmentation on face videos, a field that has not been investigated before. By evaluating on the 300VW dataset, we show that the performance of our reinforcement key scheduler outperforms that of various baselines in terms of both effective key selections and running speed. Further results on the Cityscapes dataset demonstrate that our proposed method can also generalise to other scenarios. To the best of our knowledge, this is the first work to use reinforcement learning for online key-frame decision in dynamic video segmentation, and also the first work on its application on face videos. Full Article
date Space-Efficient Vertex Separators for Treewidth. (arXiv:1907.00676v3 [cs.DS] UPDATED) By arxiv.org Published On :: For $n$-vertex graphs with treewidth $k = O(n^{1/2-epsilon})$ and an arbitrary $epsilon>0$, we present a word-RAM algorithm to compute vertex separators using only $O(n)$ bits of working memory. As an application of our algorithm, we give an $O(1)$-approximation algorithm for tree decomposition. Our algorithm computes a tree decomposition in $c^k n (log log n) log^* n$ time using $O(n)$ bits for some constant $c > 0$. We finally use the tree decomposition obtained by our algorithm to solve Vertex Cover, Independent Set, Dominating Set, MaxCut and $3$-Coloring by using $O(n)$ bits as long as the treewidth of the graph is smaller than $c' log n$ for some problem dependent constant $0 < c' < 1$. Full Article
date Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation. (arXiv:1905.00444v2 [quant-ph] UPDATED) By arxiv.org Published On :: Noisy Intermediate-Scale Quantum (NISQ) computers are entering an era in which they can perform computational tasks beyond the capabilities of the most powerful classical computers, thereby achieving "Quantum Supremacy", a major milestone in quantum computing. NISQ Supremacy requires comparison with a state-of-the-art classical simulator. We report HPC simulations of hard random quantum circuits (RQC), which have been recently used as a benchmark for the first experimental demonstration of Quantum Supremacy, sustaining an average performance of 281 Pflop/s (true single precision) on Summit, currently the fastest supercomputer in the World. These simulations were carried out using qFlex, a tensor-network-based classical high-performance simulator of RQCs. Our results show an advantage of many orders of magnitude in energy consumption of NISQ devices over classical supercomputers. In addition, we propose a standard benchmark for NISQ computers based on qFlex. Full Article
date Parameterised Counting in Logspace. (arXiv:1904.12156v3 [cs.LO] UPDATED) By arxiv.org Published On :: Stockhusen and Tantau (IPEC 2013) defined the operators paraW and paraBeta for parameterised space complexity classes by allowing bounded nondeterminism with multiple read and read-once access, respectively. Using these operators, they obtained characterisations for the complexity of many parameterisations of natural problems on graphs. In this article, we study the counting versions of such operators and introduce variants based on tail-nondeterminism, paraW[1] and paraBetaTail, in the setting of parameterised logarithmic space. We examine closure properties of the new classes under the central reductions and arithmetic operations. We also identify a wide range of natural complete problems for our classes in the areas of walk counting in digraphs, first-order model-checking and graph-homomorphisms. In doing so, we also see that the closure of #paraBetaTail-L under parameterised logspace parsimonious reductions coincides with #paraBeta-L. We show that the complexity of a parameterised variant of the determinant function is #paraBetaTail-L-hard and can be written as the difference of two functions in #paraBetaTail-L for (0,1)-matrices. Finally, we characterise the new complexity classes in terms of branching programs. Full Article
date On analog quantum algorithms for the mixing of Markov chains. (arXiv:1904.11895v2 [quant-ph] UPDATED) By arxiv.org Published On :: The problem of sampling from the stationary distribution of a Markov chain finds widespread applications in a variety of fields. The time required for a Markov chain to converge to its stationary distribution is known as the classical mixing time. In this article, we deal with analog quantum algorithms for mixing. First, we provide an analog quantum algorithm that given a Markov chain, allows us to sample from its stationary distribution in a time that scales as the sum of the square root of the classical mixing time and the square root of the classical hitting time. Our algorithm makes use of the framework of interpolated quantum walks and relies on Hamiltonian evolution in conjunction with von Neumann measurements. There also exists a different notion for quantum mixing: the problem of sampling from the limiting distribution of quantum walks, defined in a time-averaged sense. In this scenario, the quantum mixing time is defined as the time required to sample from a distribution that is close to this limiting distribution. Recently we provided an upper bound on the quantum mixing time for Erd"os-Renyi random graphs [Phys. Rev. Lett. 124, 050501 (2020)]. Here, we also extend and expand upon our findings therein. Namely, we provide an intuitive understanding of the state-of-the-art random matrix theory tools used to derive our results. In particular, for our analysis we require information about macroscopic, mesoscopic and microscopic statistics of eigenvalues of random matrices which we highlight here. Furthermore, we provide numerical simulations that corroborate our analytical findings and extend this notion of mixing from simple graphs to any ergodic, reversible, Markov chain. Full Article
date A Fast and Accurate Algorithm for Spherical Harmonic Analysis on HEALPix Grids with Applications to the Cosmic Microwave Background Radiation. (arXiv:1904.10514v4 [math.NA] UPDATED) By arxiv.org Published On :: The Hierarchical Equal Area isoLatitude Pixelation (HEALPix) scheme is used extensively in astrophysics for data collection and analysis on the sphere. The scheme was originally designed for studying the Cosmic Microwave Background (CMB) radiation, which represents the first light to travel during the early stages of the universe's development and gives the strongest evidence for the Big Bang theory to date. Refined analysis of the CMB angular power spectrum can lead to revolutionary developments in understanding the nature of dark matter and dark energy. In this paper, we present a new method for performing spherical harmonic analysis for HEALPix data, which is a central component to computing and analyzing the angular power spectrum of the massive CMB data sets. The method uses a novel combination of a non-uniform fast Fourier transform, the double Fourier sphere method, and Slevinsky's fast spherical harmonic transform (Slevinsky, 2019). For a HEALPix grid with $N$ pixels (points), the computational complexity of the method is $mathcal{O}(Nlog^2 N)$, with an initial set-up cost of $mathcal{O}(N^{3/2}log N)$. This compares favorably with $mathcal{O}(N^{3/2})$ runtime complexity of the current methods available in the HEALPix software when multiple maps need to be analyzed at the same time. Using numerical experiments, we demonstrate that the new method also appears to provide better accuracy over the entire angular power spectrum of synthetic data when compared to the current methods, with a convergence rate at least two times higher. Full Article
date Constrained Restless Bandits for Dynamic Scheduling in Cyber-Physical Systems. (arXiv:1904.08962v3 [cs.SY] UPDATED) By arxiv.org Published On :: Restless multi-armed bandits are a class of discrete-time stochastic control problems which involve sequential decision making with a finite set of actions (set of arms). This paper studies a class of constrained restless multi-armed bandits (CRMAB). The constraints are in the form of time varying set of actions (set of available arms). This variation can be either stochastic or semi-deterministic. Given a set of arms, a fixed number of them can be chosen to be played in each decision interval. The play of each arm yields a state dependent reward. The current states of arms are partially observable through binary feedback signals from arms that are played. The current availability of arms is fully observable. The objective is to maximize long term cumulative reward. The uncertainty about future availability of arms along with partial state information makes this objective challenging. Applications for CRMAB abound in the domain of cyber-physical systems. This optimization problem is analyzed using Whittle's index policy. To this end, a constrained restless single-armed bandit is studied. It is shown to admit a threshold-type optimal policy, and is also indexable. An algorithm to compute Whittle's index is presented. Further, upper bounds on the value function are derived in order to estimate the degree of sub-optimality of various solutions. The simulation study compares the performance of Whittle's index, modified Whittle's index and myopic policies. Full Article
date Fast Cross-validation in Harmonic Approximation. (arXiv:1903.10206v3 [math.NA] UPDATED) By arxiv.org Published On :: Finding a good regularization parameter for Tikhonov regularization problems is a though yet often asked question. One approach is to use leave-one-out cross-validation scores to indicate the goodness of fit. This utilizes only the noisy function values but, on the downside, comes with a high computational cost. In this paper we present a general approach to shift the main computations from the function in question to the node distribution and, making use of FFT and FFT-like algorithms, even reduce this cost tremendously to the cost of the Tikhonov regularization problem itself. We apply this technique in different settings on the torus, the unit interval, and the two-dimensional sphere. Given that the sampling points satisfy a quadrature rule our algorithm computes the cross-validations scores in floating-point precision. In the cases of arbitrarily scattered nodes we propose an approximating algorithm with the same complexity. Numerical experiments indicate the applicability of our algorithms. Full Article
date Ranked List Loss for Deep Metric Learning. (arXiv:1903.03238v6 [cs.CV] UPDATED) By arxiv.org Published On :: The objective of deep metric learning (DML) is to learn embeddings that can capture semantic similarity and dissimilarity information among data points. Existing pairwise or tripletwise loss functions used in DML are known to suffer from slow convergence due to a large proportion of trivial pairs or triplets as the model improves. To improve this, ranking-motivated structured losses are proposed recently to incorporate multiple examples and exploit the structured information among them. They converge faster and achieve state-of-the-art performance. In this work, we unveil two limitations of existing ranking-motivated structured losses and propose a novel ranked list loss to solve both of them. First, given a query, only a fraction of data points is incorporated to build the similarity structure. To address this, we propose to build a set-based similarity structure by exploiting all instances in the gallery. The learning setting can be interpreted as few-shot retrieval: given a mini-batch, every example is iteratively used as a query, and the rest ones compose the galley to search, i.e., the support set in few-shot setting. The rest examples are split into a positive set and a negative set. For every mini-batch, the learning objective of ranked list loss is to make the query closer to the positive set than to the negative set by a margin. Second, previous methods aim to pull positive pairs as close as possible in the embedding space. As a result, the intraclass data distribution tends to be extremely compressed. In contrast, we propose to learn a hypersphere for each class in order to preserve useful similarity structure inside it, which functions as regularisation. Extensive experiments demonstrate the superiority of our proposal by comparing with the state-of-the-art methods on the fine-grained image retrieval task. Full Article
date Keeping out the Masses: Understanding the Popularity and Implications of Internet Paywalls. (arXiv:1903.01406v4 [cs.CY] UPDATED) By arxiv.org Published On :: Funding the production of quality online content is a pressing problem for content producers. The most common funding method, online advertising, is rife with well-known performance and privacy harms, and an intractable subject-agent conflict: many users do not want to see advertisements, depriving the site of needed funding. Because of these negative aspects of advertisement-based funding, paywalls are an increasingly popular alternative for websites. This shift to a "pay-for-access" web is one that has potentially huge implications for the web and society. Instead of a system where information (nominally) flows freely, paywalls create a web where high quality information is available to fewer and fewer people, leaving the rest of the web users with less information, that might be also less accurate and of lower quality. Despite the potential significance of a move from an "advertising-but-open" web to a "paywalled" web, we find this issue understudied. This work addresses this gap in our understanding by measuring how widely paywalls have been adopted, what kinds of sites use paywalls, and the distribution of policies enforced by paywalls. A partial list of our findings include that (i) paywall use is accelerating (2x more paywalls every 6 months), (ii) paywall adoption differs by country (e.g. 18.75% in US, 12.69% in Australia), (iii) paywalls change how users interact with sites (e.g. higher bounce rates, less incoming links), (iv) the median cost of an annual paywall access is $108 per site, and (v) paywalls are in general trivial to circumvent. Finally, we present the design of a novel, automated system for detecting whether a site uses a paywall, through the combination of runtime browser instrumentation and repeated programmatic interactions with the site. We intend this classifier to augment future, longitudinal measurements of paywall use and behavior. Full Article
date Deterministic Sparse Fourier Transform with an ell_infty Guarantee. (arXiv:1903.00995v3 [cs.DS] UPDATED) By arxiv.org Published On :: In this paper we revisit the deterministic version of the Sparse Fourier Transform problem, which asks to read only a few entries of $x in mathbb{C}^n$ and design a recovery algorithm such that the output of the algorithm approximates $hat x$, the Discrete Fourier Transform (DFT) of $x$. The randomized case has been well-understood, while the main work in the deterministic case is that of Merhi et al.@ (J Fourier Anal Appl 2018), which obtains $O(k^2 log^{-1}k cdot log^{5.5}n)$ samples and a similar runtime with the $ell_2/ell_1$ guarantee. We focus on the stronger $ell_{infty}/ell_1$ guarantee and the closely related problem of incoherent matrices. We list our contributions as follows. 1. We find a deterministic collection of $O(k^2 log n)$ samples for the $ell_infty/ell_1$ recovery in time $O(nk log^2 n)$, and a deterministic collection of $O(k^2 log^2 n)$ samples for the $ell_infty/ell_1$ sparse recovery in time $O(k^2 log^3n)$. 2. We give new deterministic constructions of incoherent matrices that are row-sampled submatrices of the DFT matrix, via a derandomization of Bernstein's inequality and bounds on exponential sums considered in analytic number theory. Our first construction matches a previous randomized construction of Nelson, Nguyen and Woodruff (RANDOM'12), where there was no constraint on the form of the incoherent matrix. Our algorithms are nearly sample-optimal, since a lower bound of $Omega(k^2 + k log n)$ is known, even for the case where the sensing matrix can be arbitrarily designed. A similar lower bound of $Omega(k^2 log n/ log k)$ is known for incoherent matrices. Full Article
date Asymptotic expansions of eigenvalues by both the Crouzeix-Raviart and enriched Crouzeix-Raviart elements. (arXiv:1902.09524v2 [math.NA] UPDATED) By arxiv.org Published On :: Asymptotic expansions are derived for eigenvalues produced by both the Crouzeix-Raviart element and the enriched Crouzeix--Raviart element. The expansions are optimal in the sense that extrapolation eigenvalues based on them admit a fourth order convergence provided that exact eigenfunctions are smooth enough. The major challenge in establishing the expansions comes from the fact that the canonical interpolation of both nonconforming elements lacks a crucial superclose property, and the nonconformity of both elements. The main idea is to employ the relation between the lowest-order mixed Raviart--Thomas element and the two nonconforming elements, and consequently make use of the superclose property of the canonical interpolation of the lowest-order mixed Raviart--Thomas element. To overcome the difficulty caused by the nonconformity, the commuting property of the canonical interpolation operators of both nonconforming elements is further used, which turns the consistency error problem into an interpolation error problem. Then, a series of new results are obtained to show the final expansions. Full Article
date Machine learning topological phases in real space. (arXiv:1901.01963v4 [cond-mat.mes-hall] UPDATED) By arxiv.org Published On :: We develop a supervised machine learning algorithm that is able to learn topological phases for finite condensed matter systems from bulk data in real lattice space. The algorithm employs diagonalization in real space together with any supervised learning algorithm to learn topological phases through an eigenvector ensembling procedure. We combine our algorithm with decision trees and random forests to successfully recover topological phase diagrams of Su-Schrieffer-Heeger (SSH) models from bulk lattice data in real space and show how the Shannon information entropy of ensembles of lattice eigenvectors can be used to retrieve a signal detailing how topological information is distributed in the bulk. The discovery of Shannon information entropy signals associated with topological phase transitions from the analysis of data from several thousand SSH systems illustrates how model explainability in machine learning can advance the research of exotic quantum materials with properties that may power future technological applications such as qubit engineering for quantum computing. Full Article
date Learning Direct Optimization for Scene Understanding. (arXiv:1812.07524v2 [cs.CV] UPDATED) By arxiv.org Published On :: We develop a Learning Direct Optimization (LiDO) method for the refinement of a latent variable model that describes input image x. Our goal is to explain a single image x with an interpretable 3D computer graphics model having scene graph latent variables z (such as object appearance, camera position). Given a current estimate of z we can render a prediction of the image g(z), which can be compared to the image x. The standard way to proceed is then to measure the error E(x, g(z)) between the two, and use an optimizer to minimize the error. However, it is unknown which error measure E would be most effective for simultaneously addressing issues such as misaligned objects, occlusions, textures, etc. In contrast, the LiDO approach trains a Prediction Network to predict an update directly to correct z, rather than minimizing the error with respect to z. Experiments show that our LiDO method converges rapidly as it does not need to perform a search on the error landscape, produces better solutions than error-based competitors, and is able to handle the mismatch between the data and the fitted scene model. We apply LiDO to a realistic synthetic dataset, and show that the method also transfers to work well with real images. Full Article
date Weighted Moore-Penrose inverses of arbitrary-order tensors. (arXiv:1812.03052v3 [math.NA] UPDATED) By arxiv.org Published On :: Within the field of multilinear algebra, inverses and generalized inverses of tensors based on the Einstein product have been investigated over the past few years. In this paper, we explore the singular value decomposition and full-rank decomposition of arbitrary-order tensors using {it reshape} operation. Applying range and null space of tensors along with the reshape operation; we further study the Moore-Penrose inverse of tensors and their cancellation properties via the Einstein product. Then we discuss weighted Moore-Penrose inverses of arbitrary-order tensors using such product. Following a specific algebraic approach, a few characterizations and representations of these inverses are explored. In addition to this, we obtain a few necessary and sufficient conditions for the reverse-order law to hold for weighted Moore-Penrose inverses of arbitrary-order tensors. Full Article
date Performance of the smallest-variance-first rule in appointment sequencing. (arXiv:1812.01467v4 [math.PR] UPDATED) By arxiv.org Published On :: A classical problem in appointment scheduling, with applications in health care, concerns the determination of the patients' arrival times that minimize a cost function that is a weighted sum of mean waiting times and mean idle times. One aspect of this problem is the sequencing problem, which focuses on ordering the patients. We assess the performance of the smallest-variance-first (SVF) rule, which sequences patients in order of increasing variance of their service durations. While it was known that SVF is not always optimal, it has been widely observed that it performs well in practice and simulation. We provide a theoretical justification for this observation by proving, in various settings, quantitative worst-case bounds on the ratio between the cost incurred by the SVF rule and the minimum attainable cost. We also show that, in great generality, SVF is asymptotically optimal, i.e., the ratio approaches 1 as the number of patients grows large. While evaluating policies by considering an approximation ratio is a standard approach in many algorithmic settings, our results appear to be the first of this type in the appointment scheduling literature. Full Article
date An improved exact algorithm and an NP-completeness proof for sparse matrix bipartitioning. (arXiv:1811.02043v2 [cs.DS] UPDATED) By arxiv.org Published On :: We investigate sparse matrix bipartitioning -- a problem where we minimize the communication volume in parallel sparse matrix-vector multiplication. We prove, by reduction from graph bisection, that this problem is $mathcal{NP}$-complete in the case where each side of the bipartitioning must contain a linear fraction of the nonzeros. We present an improved exact branch-and-bound algorithm which finds the minimum communication volume for a given matrix and maximum allowed imbalance. The algorithm is based on a maximum-flow bound and a packing bound, which extend previous matching and packing bounds. We implemented the algorithm in a new program called MP (Matrix Partitioner), which solved 839 matrices from the SuiteSparse collection to optimality, each within 24 hours of CPU-time. Furthermore, MP solved the difficult problem of the matrix cage6 in about 3 days. The new program is on average more than ten times faster than the previous program MondriaanOpt. Benchmark results using the set of 839 optimally solved matrices show that combining the medium-grain/iterative refinement methods of the Mondriaan package with the hypergraph bipartitioner of the PaToH package produces sparse matrix bipartitionings on average within 10% of the optimal solution. Full Article
date SilhoNet: An RGB Method for 6D Object Pose Estimation. (arXiv:1809.06893v4 [cs.CV] UPDATED) By arxiv.org Published On :: Autonomous robot manipulation involves estimating the translation and orientation of the object to be manipulated as a 6-degree-of-freedom (6D) pose. Methods using RGB-D data have shown great success in solving this problem. However, there are situations where cost constraints or the working environment may limit the use of RGB-D sensors. When limited to monocular camera data only, the problem of object pose estimation is very challenging. In this work, we introduce a novel method called SilhoNet that predicts 6D object pose from monocular images. We use a Convolutional Neural Network (CNN) pipeline that takes in Region of Interest (ROI) proposals to simultaneously predict an intermediate silhouette representation for objects with an associated occlusion mask and a 3D translation vector. The 3D orientation is then regressed from the predicted silhouettes. We show that our method achieves better overall performance on the YCB-Video dataset than two state-of-the art networks for 6D pose estimation from monocular image input. Full Article
date Identifying Compromised Accounts on Social Media Using Statistical Text Analysis. (arXiv:1804.07247v3 [cs.SI] UPDATED) By arxiv.org Published On :: Compromised accounts on social networks are regular user accounts that have been taken over by an entity with malicious intent. Since the adversary exploits the already established trust of a compromised account, it is crucial to detect these accounts to limit the damage they can cause. We propose a novel general framework for discovering compromised accounts by semantic analysis of text messages coming out from an account. Our framework is built on the observation that normal users will use language that is measurably different from the language that an adversary would use when the account is compromised. We use our framework to develop specific algorithms that use the difference of language models of users and adversaries as features in a supervised learning setup. Evaluation results show that the proposed framework is effective for discovering compromised accounts on social networks and a KL-divergence-based language model feature works best. Full Article
date ZebraLancer: Decentralized Crowdsourcing of Human Knowledge atop Open Blockchain. (arXiv:1803.01256v5 [cs.HC] UPDATED) By arxiv.org Published On :: We design and implement the first private and anonymous decentralized crowdsourcing system ZebraLancer, and overcome two fundamental challenges of decentralizing crowdsourcing, i.e., data leakage and identity breach. First, our outsource-then-prove methodology resolves the tension between the blockchain transparency and the data confidentiality to guarantee the basic utilities/fairness requirements of data crowdsourcing, thus ensuring: (i) a requester will not pay more than what data deserve, according to a policy announced when her task is published via the blockchain; (ii) each worker indeed gets a payment based on the policy, if he submits data to the blockchain; (iii) the above properties are realized not only without a central arbiter, but also without leaking the data to the open blockchain. Second, the transparency of blockchain allows one to infer private information about workers and requesters through their participation history. Simply enabling anonymity is seemingly attempting but will allow malicious workers to submit multiple times to reap rewards. ZebraLancer also overcomes this problem by allowing anonymous requests/submissions without sacrificing accountability. The idea behind is a subtle linkability: if a worker submits twice to a task, anyone can link the submissions, or else he stays anonymous and unlinkable across tasks. To realize this delicate linkability, we put forward a novel cryptographic concept, i.e., the common-prefix-linkable anonymous authentication. We remark the new anonymous authentication scheme might be of independent interest. Finally, we implement our protocol for a common image annotation task and deploy it in a test net of Ethereum. The experiment results show the applicability of our protocol atop the existing real-world blockchain. Full Article
date ErdH{o}s-P'osa property of chordless cycles and its applications. (arXiv:1711.00667v3 [math.CO] UPDATED) By arxiv.org Published On :: A chordless cycle, or equivalently a hole, in a graph $G$ is an induced subgraph of $G$ which is a cycle of length at least $4$. We prove that the ErdH{o}s-P'osa property holds for chordless cycles, which resolves the major open question concerning the ErdH{o}s-P'osa property. Our proof for chordless cycles is constructive: in polynomial time, one can find either $k+1$ vertex-disjoint chordless cycles, or $c_1k^2 log k+c_2$ vertices hitting every chordless cycle for some constants $c_1$ and $c_2$. It immediately implies an approximation algorithm of factor $mathcal{O}(sf{opt}log {sf opt})$ for Chordal Vertex Deletion. We complement our main result by showing that chordless cycles of length at least $ell$ for any fixed $ellge 5$ do not have the ErdH{o}s-P'osa property. Full Article
date Using hierarchical matrices in the solution of the time-fractional heat equation by multigrid waveform relaxation. (arXiv:1706.07632v3 [math.NA] UPDATED) By arxiv.org Published On :: This work deals with the efficient numerical solution of the time-fractional heat equation discretized on non-uniform temporal meshes. Non-uniform grids are essential to capture the singularities of "typical" solutions of time-fractional problems. We propose an efficient space-time multigrid method based on the waveform relaxation technique, which accounts for the nonlocal character of the fractional differential operator. To maintain an optimal complexity, which can be obtained for the case of uniform grids, we approximate the coefficient matrix corresponding to the temporal discretization by its hierarchical matrix (${cal H}$-matrix) representation. In particular, the proposed method has a computational cost of ${cal O}(k N M log(M))$, where $M$ is the number of time steps, $N$ is the number of spatial grid points, and $k$ is a parameter which controls the accuracy of the ${cal H}$-matrix approximation. The efficiency and the good convergence of the algorithm, which can be theoretically justified by a semi-algebraic mode analysis, are demonstrated through numerical experiments in both one- and two-dimensional spaces. Full Article
date Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity. (arXiv:1706.02205v4 [math.NA] UPDATED) By arxiv.org Published On :: Dense kernel matrices $Theta in mathbb{R}^{N imes N}$ obtained from point evaluations of a covariance function $G$ at locations ${ x_{i} }_{1 leq i leq N} subset mathbb{R}^{d}$ arise in statistics, machine learning, and numerical analysis. For covariance functions that are Green's functions of elliptic boundary value problems and homogeneously-distributed sampling points, we show how to identify a subset $S subset { 1 , dots , N }^2$, with $# S = O ( N log (N) log^{d} ( N /epsilon ) )$, such that the zero fill-in incomplete Cholesky factorisation of the sparse matrix $Theta_{ij} 1_{( i, j ) in S}$ is an $epsilon$-approximation of $Theta$. This factorisation can provably be obtained in complexity $O ( N log( N ) log^{d}( N /epsilon) )$ in space and $O ( N log^{2}( N ) log^{2d}( N /epsilon) )$ in time, improving upon the state of the art for general elliptic operators; we further present numerical evidence that $d$ can be taken to be the intrinsic dimension of the data set rather than that of the ambient space. The algorithm only needs to know the spatial configuration of the $x_{i}$ and does not require an analytic representation of $G$. Furthermore, this factorization straightforwardly provides an approximate sparse PCA with optimal rate of convergence in the operator norm. Hence, by using only subsampling and the incomplete Cholesky factorization, we obtain, at nearly linear complexity, the compression, inversion and approximate PCA of a large class of covariance matrices. By inverting the order of the Cholesky factorization we also obtain a solver for elliptic PDE with complexity $O ( N log^{d}( N /epsilon) )$ in space and $O ( N log^{2d}( N /epsilon) )$ in time, improving upon the state of the art for general elliptic operators. Full Article
date 5 Simple Tips for How to Update Content on Your Website By feedproxy.google.com Published On :: Mon, 13 Jan 2020 21:30:41 +0000 Subscribe to our YouTube channel for the latest in digital marketing! Transcript: Your website isn’t set in stone, so you shouldn’t treat it like it is. Technology and the internet change quickly, and often. You should update your website regularly to keep up with the times. Having an up-to-date and optimized site creates a great […] The post 5 Simple Tips for How to Update Content on Your Website appeared first on WebFX Blog. Full Article Web Design
date Is My Website ADA Compliant? How to Check (and Update) Your Site By feedproxy.google.com Published On :: Tue, 11 Feb 2020 14:00:55 +0000 What do Amazon, Hershey’s, and The Wall Street Journal have in common? They’ve all gotten named in lawsuits related to website accessibility and the Americans with Disabilities Act (ADA). They aren’t alone, either. In 2018, more than 2000 website accessibility lawsuits (a 177% increase from 2017) got filed, emphasizing the increased importance and focus on […] The post Is My Website ADA Compliant? How to Check (and Update) Your Site appeared first on WebFX Blog. Full Article Web Design
date Coronavirus update: UW busy with testing, new guidelines for visiting grandma and other COVID-19 headlines By www.inlander.com Published On :: Tue, 10 Mar 2020 12:53:00 -0700 Coronavirus Family Tree The University of Washington Virology lab, which is testing samples for coronavirus, tweeted last night.… Full Article News/Local News
date UPDATED: Spokane Veterans Home isolated residents back in February due to respiratory illness — with no way to test By www.inlander.com Published On :: Thu, 23 Apr 2020 15:15:00 -0700 UPDATE: The Department of Veterans Affairs announced after this article was first published that Spokane Veterans Home residents with COVID-19 would be moved to the Mann-Grandstaff VA Medical Center.… Full Article News/Local News
date Supreme Court divided over Obamacare’s contraceptive mandate By www.inlander.com Published On :: Wed, 06 May 2020 17:40:24 -0700 By Adam Liptak The New York Times Company… Full Article Local News
date A first-timer hits the Bloomsday course on its original date and walks away with some memories - barely By www.inlander.com Published On :: Thu, 07 May 2020 01:33:00 -0700 The chafing.… Full Article Culture/Arts & Culture
date Providing answers to questions using logical synthesis of candidate answers By www.freepatentsonline.com Published On :: Tue, 19 May 2015 08:00:00 EDT A method, system and computer program product for generating answers to questions. In one embodiment, the method comprises receiving an input query, decomposing the input query into a plurality of different subqueries, and conducting a search in one or more data sources to identify at least one candidate answer to each of the subqueries. A ranking function is applied to each of the candidate answers to determine a ranking for each of these candidate answers; and for each of the subqueries, one of the candidate answers to the subquery is selected based on this ranking. A logical synthesis component is applied to synthesize a candidate answer for the input query from the selected the candidate answers to the subqueries. In one embodiment, the procedure applied by the logical synthesis component to synthesize the candidate answer for the input query is determined from the input query. Full Article
date Firmware update method and apparatus of set-top box for digital broadcast system By www.freepatentsonline.com Published On :: Tue, 03 Nov 2015 08:00:00 EST A firmware update method and apparatus of a set-top box for a digital broadcast system is provided. A firmware update method of a set-top box for a digital broadcast system includes determining whether a newly received Code Version Table (CVT) following a public CVT which has been previously received and stored is the public CVT or a filtering CVT; and updating, when the newly received CVG is the filtering CVT, the firmware of the set-top box with a filtering firmware indicated by the filtering CVT. Full Article
date Calendar watch having a centrally pivoted date indicator By www.freepatentsonline.com Published On :: Tue, 27 Nov 1990 08:00:00 EST A calendar watch includes a central date indicator (4). The indicator is united with a crown wheel (9) comprising teeth (11) forming a circular crown (12) arranged to be perpendicular to a face (13) of said wheel. The teeth (12) are driven by a finger (14) rotating in a plane intersecting said crown in its height. The finger is united with a date driving wheel (15). The invention permits easy transformation of a watch having its date display in a dial aperture to a watch having a date indicator rotating about the center of the movement. Full Article
date Method and apparatus for controlling update of digital pre-distortion coefficient By www.freepatentsonline.com Published On :: Tue, 19 May 2015 08:00:00 EDT A method and apparatus for controlling update of digital pre-distortion (DPD) coefficient is provided. The apparatus is applicable to a digital power control system, wherein the apparatus comprises: an update controlling unit configured to determine a group of fully-trained DPD coefficients among a plurality of DPD coefficients; and a DPD coefficient generating unit configured to update adaptively the group of fully-trained DPD coefficients according to the result of judgment of the update controlling unit. The DPD coefficients are allowed to be updated after being judged as being able to be fully trained according to power distribution information of DPD input signals, or according to address distribution information of an LUT, or according to average power of output of an HPA; otherwise, they may not be updated, thereby efficiently preventing DPD abnormality resulted from unfull training of coefficients in being updated. Full Article
date Wound dressing inhibiting lateral diffusion of absorbed exudate By www.freepatentsonline.com Published On :: Tue, 19 May 2015 08:00:00 EDT A wound dressing including a hydrophilic layer and a hydrophobic layer is described. The hydrophilic layer absorbs exudate from a wound and the hydrophobic layer absorbs the exudate from the hydrophilic layer and traps the exudate. Because the hydrophilic layer is used adjacent to the wound, the exudate is readily absorbed thereby reducing the risk of maceration and infection of the wound tissue by the exudate. The hydrophobic layer receives the absorbed exudate from the hydrophilic layer and traps the exudate through an interaction that in turn prevents lateral diffusion of the exudate through the bandage to healthy portions of the skin. The hydrophilic and hydrophobic layers are fabricated from polymer fibers that can be spun to include components that facilitate wound healing, such as poly(hexamethylene biguanide) and/or hyaluronic acid. Full Article
date Methods for producing multiple food extrudates By www.freepatentsonline.com Published On :: Tue, 12 May 2015 08:00:00 EDT An apparatus for forming a single extrudable food stream such as a cooked cereal dough into a plurality of differently colored and/or flavored dough streams is disclosed including an extruder having screw augers for advancing a plastic food mass, a head or manifold for dividing the plastic food mass into a plurality of substreams each in turn in fluid communication with a plurality of sub-divided dough passageways, and a die head having a plurality of die ports. Each subpassage is separately supplied an additive and has disposed therein a multiplicity of in-line static mixer elements to admix the additive into the substreams of the plastic food mass before passage through the die ports. In a preferred form, first and second substreams are intermixed in a non-homogenous manner before reaching the exit ports. The extrudates are severed into individual pieces by a rotary cutter. Full Article
date Methods, systems and devices for generating real-time activity data updates to display devices By www.freepatentsonline.com Published On :: Tue, 10 Feb 2015 08:00:00 EST Methods, systems and devices are provided for displaying monitored activity data in substantial real-time on a screen of a computing device. One example method includes capturing motion data associated with activity of a user via an activity tracking device. The motion data is quantified into a plurality of metrics associated with the activity of the user. The method includes connecting the activity tracking device with a computing device over a wireless data connection, and sending motion data from the activity tracking device to the computing device for display of one or more of the plurality of metrics on a graphical user interface of the computing device. At least one of the plurality of metrics displayed on the graphical user interface is shown to change in substantial real-time based on the motion data. Full Article
date TEMPORAL MOTION DATA CANDIDATE DERIVATION IN VIDEO CODING By www.freepatentsonline.com Published On :: Thu, 29 Jun 2017 08:00:00 EDT A method for derivation of a temporal motion data (TMD) candidate for a prediction unit (PU) in video encoding or video decoding is provided. The derived TMD candidate is for inclusion in an inter-prediction candidate list for the PU. The method includes determining a primary TMD position relative to a co-located PU in a co-located largest coding unit (LCU), wherein the co-located PU is a block in a reference picture having a same size, shape, and coordinates as the PU, and selecting at least some motion data of a secondary TMD position as the TMD candidate when the primary TMD position is in a bottom neighboring LCU or in a bottom right neighboring LCU of the co-located LCU, wherein the secondary TMD position is determined relative to the co-located PU. Full Article
date AUTOMATIC GENERATION OF VALIDATORS TO VALIDATE DEPLOYMENT CODE USED FOR CONFIGURING SERVERS By www.freepatentsonline.com Published On :: Thu, 22 Jun 2017 08:00:00 EDT A validation system is configured to automatically generate validators for one or more target systems. The validation system includes: a memory storing a computer process, a network interface configured to interface with the one or more target systems over a computer network, and a processor executing the computer process. The computer process is configured to parse the deployment code to identify components in deployment code, generate validator code for each identified component, and use the network interface to transmit the validator codes to the one or more target systems. Full Article
date ANALYZING DEPLOYMENT PIPELINES USED TO UPDATE PRODUCTION COMPUTING SERVICES USING A LIVE PIPELINE TEMPLATE PROCESS By www.freepatentsonline.com Published On :: Thu, 22 Jun 2017 08:00:00 EDT Techniques are presented for managing a deployment pipeline using an inheritable and extensible source code template—generally referred to as a live pipeline template (LPT). As described, live pipeline templates may be used to manage deployment pipelines which, in turn, are used to launch, maintain, and update the services and systems used to host and provide computing services. Full Article
date UPDATE SYSTEM FOR LINUX OPERATING SYSTEM AND METHOD THEREOF By www.freepatentsonline.com Published On :: Thu, 29 Jun 2017 08:00:00 EDT An update system for the Linux operating system and a method thereof are disclosed. In the system and method, an update program can be obtained via distributed clients, to reduce a server's loading. When updating the operating system, allocation data on a user data sector is backed up and restored, so as to complete the update for the operating system. With the present technical features, the technical effect of backing up and restoring the allocation data on the user data sector, and reducing the loading of the server can be achieved. Full Article
date Lead-free pyrotechnic and primary explosive compositions containing metal iodates By www.freepatentsonline.com Published On :: Tue, 12 Aug 2014 08:00:00 EDT A lead-free pyrotechnic and primary explosive compositions including metal iodates as an oxidizer in nanocomposite energetic compositions including metal powder fuel. Full Article
date Orchestration of Date Query Processing in a Database System By www.freepatentsonline.com Published On :: Thu, 29 Jun 2017 08:00:00 EDT In one embodiment, a method receives a query for data in a database system and calls a plurality of engines to analyze information for the query. A calculation graph is generated from at least a portion of the plurality of engines where each of the at least a portion of the plurality of engines add a node to the calculation graph based on analyzing of the information for the query. Then, the method executes the query by calling the nodes of the calculation graph. Each node uses metadata added to the node from a respective calculation engine to perform a calculation for the node. Then, a result of the query is output based on the respective calculations performed by the nodes. Full Article
date LANTHANUM MOLYBDATE ABRADABLE COATINGS, THEIR METHODS OF FORMATION AND USE By www.freepatentsonline.com Published On :: Thu, 29 Jun 2017 08:00:00 EDT A coated substrate is provided that can include a substrate defining a surface, and an abradable coating on the surface of the substrate. The abradable coating can comprise La2-xAxMo2-y-y' WyBy'O9-δ forming a crystalline structure, where A comprises Li, Na, K, Rb, Cs, Sc, Y, Ce, Pr, Nd, Pm, Sm, Eu, Gd, Tb, Dy, Ho, Er, Tm, Yb, Lu, Th, Be, Mg, Ca, Sr, Ba, Cu, Bi, Cd, Zn, Ag, Au, Pt, Ir, Rh, Ru, Pd, or combinations thereof; 0 Full Article
date Updated: Despite Receiving a $50 Million Donation, Children's Hospital Oakland Is Still Refusing to Give Raises By www.eastbayexpress.com Published On :: Wed, 04 Jun 2014 15:54:00 -0700 If you happen to run into any medical residents anytime soon, they may look a little fatigued and broke, especially if they happen to be residents or pediatricians of UCSF Benioff Children’s Hospital of Oakland. Today, the CIR/SEIU Healthcare union that represents resident physicians and pediatricians said it plans to rally in front of the hospital on Friday at 12:15 p.m. along with nurses and community leaders to demand better wagers and working conditions.… Full Article Blogs/News
date Former Southampton boss Ronald Koeman posts a positive update after health scare By www.dailyecho.co.uk Published On :: Fri, 08 May 2020 08:03:11 +0100 FORMER Saints manager Ronald Koeman took to Twitter to thank everyone for their support after undergoing a heart procedure last Sunday. Full Article
date Rearranged dates at The Concorde Club By www.dailyecho.co.uk Published On :: Wed, 01 Apr 2020 05:11:00 +0100 THE Concorde Club has rearranged a host of gigs and events. Full Article
date Official Queen tribute mark iconic band's half century with Southampton date in 2021 By www.dailyecho.co.uk Published On :: Thu, 02 Apr 2020 05:09:39 +0100 QUEEN Extravaganza, the official Queen tribute band produced by Roger Taylor and Brian May, returns to the UK in 2021 following sell out shows across the globe. It celebrates 50 years of Queen with a one night only show at Mayflower Theatre on Sunday January 31 among 26 dates across the UK. Full Article
date REVIEW: Mercury Prize nominee Michael Kiwanuka confirms he's living in Southampton at Guildhall date By www.dailyecho.co.uk Published On :: Tue, 03 Mar 2020 11:28:49 +0000 So now it’s officially confirmed by the man himself! After various celebrity sightings in the New Forest, Mayflower Park and Overdraft Craft Ale Bar Shirley, soul man of the moment Michael Kiwanuka dedicated a heartfelt rendition of Home Again to a sold out audience at the O2 Guildhall last night. Full Article
date TOUR DATES ARE HERE! By www.dadalife.com Published On :: Wed, 14 Mar 2018 18:12:08 +0000 Full Article Uncategorized
date Wolfenstein II: The New Colossus Switch launch date revealed By www.dailyecho.co.uk Published On :: Tue, 24 Apr 2018 18:35:44 +0100 Bethesda announced today that the Switch version of Wolfenstein II: The New Colossus will launch on Friday, June 29. Full Article