Search

We develop deterministic perturbation bounds for singular values and vectors of orthogonally decomposable tensors, in a spirit similar to classical results for matrices such as those due to Weyl, Davis, Kahan and Wedin. Our bounds demonstrate intriguing differences between matrices and higher order tensors. Most notably, they indicate that for higher order tensors perturbation affects each essential singular value/vector in isolation, and its effect on an essential singular vector does not depend on the multiplicity of its corresponding singular value or its distance from other singular values. Our results can be readily applied and provide a unified treatment to many different problems involving higher order orthogonally decomposable tensors. In particular, we illustrate the implications of our bounds through connected yet seemingly different high-dimensional data analysis tasks: the unsupervised learning scenario of tensor SVD and the supervised task of tensor regression, leading to new insights in both of these settings.

Introduction The outbreak of COVID-19 has differentially affected countries in the world, with health infrastructure and other related vulnerability indicators playing a role in determining the extent of the COVID-19 spread. Vulnerability of a geographical region/country to COVID-19 has been a topic of interest, particularly in low- and middle-income countries like India to assess the multi-factorial impact of COVID-19 on the incidence, prevalence or mortality data. Datasets and Methods Based on publicly reported socio-economic, demographic, health-based and epidemiological data from national surveys in India, we compute contextual, COVID-19 Vulnerability Indices (cVIs) across multiple thematic resolutions for different geographical and spatial administrative regions. These multi-resolution cVIs were used in regression models to assess their impact on indicators of the spread of COVID-19 such as the average time-varying instantaneous reproduction number. Results Our observational study was focused on 30 districts of the eastern Indian state of Odisha. It is an agrarian state, prone to natural disasters and one of the largest contributors of an unprotected migrant workforce. Our analyses identified housing and hygiene conditions, availability of health care and COVID preparedness as important spatial indicators. Conclusion Odisha has demonstrated success in containing the COVID-19 infection to a reasonable level with proactive measures to contain the spread of the virus during the first wave. However, with the onset of the second wave of COVID, the virus has been making inroads into the hinterlands and peripheral districts of the state, burdening the already deficient public health system in these areas. The vulnerability index presented in this paper identified vulnerable districts in Odisha. While some of them may not have a large number of COVID-19 cases at a given point of time, they could experience repercussions of the pandemic. Improved understanding of the factors driving COVID-19 vulnerability will help policy makers prioritise resources and regions leading to more effective mitigation strategies for the COVID-19 pandemic and beyond. WHAT IS ALREADY KNOWN Measuring vulnerability to COVID-19 and other pandemics is a complex and layered subject. In Low-to-Middle-Income Country (LMIC) like India, complete reliance on incidence, prevalence or mortality data of the disease may not be the best measure since this data from the health system and DHS in public domain is limited. ADDED VALUE OF THIS STUDY To our knowledge, this is the first study at the district level concerning the COVID-19 situation in Odisha, characterized by a large tribal and migrant population. We defined vulnerability through relevant socio-economic domains that have an influence on mitigation strategies. Although we applied our methods to the districts of Odisha, we believe they can be used in other LMIC regions. IMPLICATIONS OF THE FINDINGS Regions with higher overall or theme-specific vulnerability index might experience potentially severe consequences of the COVID-19 outbreak demanding precise, dynamic and nimble policy decisions to prevent a potentially dire situation.

We study a Markovian agent-based model (MABM) in this paper. Each agent is endowed with a local state that changes over time as the agent interacts with its neighbours. The neighbourhood structure is given by a graph. In a recent paper [Simon et al. 2011], the authors used the automorphisms of the underlying graph to generate a lumpable partition of the joint state space ensuring Markovianness of the lumped process for binary dynamics. However, many large random graphs tend to become asymmetric rendering the automorphism-based lumping approach ineffective as a tool of model reduction. In order to mitigate this problem, we propose a lumping method based on a notion of local symmetry, which compares only local neighbourhoods of vertices. Since local symmetry only ensures approximate lumpability, we quantify the approximation error by means of Kullback-Leibler divergence rate between the original Markov chain and a lifted Markov chain. We prove the approximation error decreases monotonically. The connections to fibrations of graphs are also discussed., Comment: 28 pages, 4 figures

In this paper, we study the estimation of a rank-one spiked tensor in the presence of heavy tailed noise. Our results highlight some of the fundamental similarities and differences in the tradeoff between statistical and computational efficiencies under heavy tailed and Gaussian noise. In particular, we show that, for $p$ th order tensors, the tradeoff manifests in an identical fashion as the Gaussian case when the noise has finite $4(p-1)$ th moment. The difference in signal strength requirements, with or without computational constraints, for us to estimate the singular vectors at the optimal rate, interestingly, narrows for noise with heavier tails and vanishes when the noise only has finite fourth moment. Moreover, if the noise has less than fourth moment, tensor SVD, perhaps the most natural approach, is suboptimal even though it is computationally intractable. Our analysis exploits a close connection between estimating the rank-one spikes and the spectral norm of a random tensor with iid entries. In particular, we show that the order of the spectral norm of a random tensor can be precisely characterized by the moment of its entries, generalizing classical results for random matrices. In addition to the theoretical guarantees, we propose estimation procedures for the heavy tailed regime, which are easy to implement and efficient to run. Numerical experiments are presented to demonstrate their practical merits., Comment: 46 pages, 7 figures