ﻻ يوجد ملخص باللغة العربية
Inspired by the quantum computing algorithms for Linear Algebra problems [HHL,TaShma] we study how the simulation on a classical computer of this type of Phase Estimation algorithms performs when we apply it to solve the Eigen-Problem of Hermitian matrices. The result is a completely new, efficient and stable, parallel algorithm to compute an approximate spectral decomposition of any Hermitian matrix. The algorithm can be implemented by Boolean circuits in $O(log^2 n)$ parallel time with a total cost of $O(n^{omega+1})$ Boolean operations. This Boolean complexity matches the best known rigorous $O(log^2 n)$ parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so further improvements may lead to practical implementations. All previous efficient and rigorous approaches to solve the Eigen-Problem use randomization to avoid bad condition as we do too. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases $(mod (2pi))$ is the main technical contribution of this work. This randomization enables us, given a Hermitian matrix with well separated eigenvalues, to sample a random eigenvalue and produce an approximate eigenvector in $O(log^2 n)$ parallel time and $O(n^omega)$ Boolean complexity. We conjecture that further improvements of our method can provide a stable solution to the full approximate spectral decomposition problem with complexity similar to the complexity (up to a logarithmic factor) of sampling a single eigenvector.
We consider a fundamental algorithmic question in spectral graph theory: Compute a spectral sparsifier of random-walk matrix-polynomial $$L_alpha(G)=D-sum_{r=1}^dalpha_rD(D^{-1}A)^r$$ where $A$ is the adjacency matrix of a weighted, undirected graph,
Correlation and similarity measures are widely used in all the areas of sciences and social sciences. Often the variables are not numbers but are instead qualitative descriptors called categorical data. We define and study similarity matrix, as a mea
Using the methods originally developed for Random Matrix Theory we derive an exact mathematical formula for number variance (introduced in [4]) describing a rigidity of particle ensembles with power-law repulsion. The resulting relation is consequent
This paper presents a novel approach to characterize the dynamics of the limit spectrum of large random matrices. This approach is based upon the notion we call spectral dominance. In particular, we show that the limit spectral measure can be determi
We analyze complex networks under random matrix theory framework. Particularly, we show that $Delta_3$ statistic, which gives information about the long range correlations among eigenvalues, provides a qualitative measure of randomness in networks. A