BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Raj Rao Nadakuditi

Raj Rao Nadakuditi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRmath.STStatistics TheoryMachine Learningcond-mat.dis-nncond-mat.stat-mechInformation Theorymath.ITphysics.soc-phSocial and Information Networksmath-phmath.MPphysics.opticsData Structures and Algorithmsmath.NAphysics.comp-ph

Catalog footprint

What is connected

17works
16topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

17 published item(s)

preprint2022arXiv

Free Component Analysis: Theory, Algorithms & Applications

We describe a method for unmixing mixtures of freely independent random variables in a manner analogous to the independent component analysis (ICA) based method for unmixing independent random variables from their additive mixtures. Random matrices play the role of free random variables in this context so the method we develop, which we call Free component analysis (FCA), unmixes matrices from additive mixtures of matrices. Thus, while the mixing model is standard, the novelty and difference in unmixing performance comes from the introduction of a new statistical criteria, derived from free probability theory, that quantify freeness analogous to how kurtosis and entropy quantify independence. We describe the theory, the various algorithms, and compare FCA to vanilla ICA which does not account for spatial or temporal structure. We highlight why the statistical criteria make FCA also vanilla despite its matricial underpinnings and show that FCA performs comparably to, and sometimes better than, (vanilla) ICA in every application, such as image and speech unmixing, where ICA has been known to succeed. Our computational experiments suggest that not-so-random matrices, such as images and short time fourier transform matrix of waveforms are (closer to being) freer "in the wild" than we might have theoretically expected.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Detection thresholds in very sparse matrix completion

Let $A$ be a rectangular matrix of size $m\times n$ and $A_1$ be the random matrix where each entry of $A$ is multiplied by an independent $\{0,1\}$-Bernoulli random variable with parameter $1/2$. This paper is about when, how and why the non-Hermitian eigen-spectra of the randomly induced asymmetric matrices $A_1 (A - A_1)^*$ and $(A-A_1)^*A_1$ captures more of the relevant information about the principal component structure of $A$ than via its SVD or the eigen-spectra of $A A^*$ and $A^* A$, respectively. Hint: the asymmetry inducing randomness breaks the echo-chamber effect that cripples the SVD. We illustrate the application of this striking phenomenon on the low-rank matrix completion problem for the setting where each entry is observed with probability $d/n$, including the very sparse regime where $d$ is of order $1$, where matrix completion via the SVD of $A$ fails or produces unreliable recovery. We determine an asymptotically exact, matrix-dependent, non-universal detection threshold above which reliable, statistically optimal matrix recovery using a new, universal data-driven matrix-completion algorithm is possible. Averaging the left and right eigenvectors provably improves the recovered matrix but not the detection threshold. We define another variant of this asymmetric procedure that bypasses the randomization step and has a detection threshold that is smaller by a constant factor but with a computational cost that is larger by a polynomial factor of the number of observed entries. Both detection thresholds shatter the seeming barrier due to the well-known information theoretical limit $d \asymp \log n$ for matrix completion found in the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Time Series Source Separation using Dynamic Mode Decomposition

The Dynamic Mode Decomposition (DMD) extracted dynamic modes are the non-orthogonal eigenvectors of the matrix that best approximates the one-step temporal evolution of the multivariate samples. In the context of dynamical system analysis, the extracted dynamic modes are a generalization of global stability modes. We apply DMD to a data matrix whose rows are linearly independent, additive mixtures of latent time series. We show that when the latent time series are uncorrelated at a lag of one time-step then, in the large sample limit, the recovered dynamic modes will approximate, up to a column-wise normalization, the columns of the mixing matrix. Thus, DMD is a time series blind source separation algorithm in disguise, but is different from closely related second order algorithms such as the Second-Order Blind Identification (SOBI) method and the Algorithm for Multiple Unknown Signals Extraction (AMUSE). All can unmix mixed stationary, ergodic Gaussian time series in a way that kurtosis-based Independent Components Analysis (ICA) fundamentally cannot. We use our insights on single lag DMD to develop a higher-lag extension, analyze the finite sample performance with and without randomly missing data, and identify settings where the higher lag variant can outperform the conventional single lag variant. We validate our results with numerical simulations, and highlight how DMD can be used in change point detection.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The transmission coefficient distribution of highly scattering sparse random media

We consider the distribution of the transmission coefficients, i.e. the singular values of the modal transmission matrix, for 2D random media with periodic boundary conditions composed of a large number of point-like non-absorbing scatterers. The scatterers are placed at random locations in the medium and have random refractive indices that are drawn from an arbitrary, known distribution. We construct a randomized model for the scattering matrix that retains scatterer dependent properties essential to reproduce the transmission coefficient distribution and analytically characterize the distribution of this matrix as a function of the refractive index distribution, the number of modes, and the number of scatterers. We show that the derived distribution agrees remarkably well with results obtained using a numerically rigorous spectrally accurate simulation. Analysis of the derived distribution provides the strongest principled justification yet of why we should expect perfect transmission in such random media regardless of the refractive index distribution of the constituent scatterers. The analysis suggests a sparsity condition under which random media will exhibit a perfect transmission-supporting universal transmission coefficient distribution in the deep medium limit.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Backscatter analysis based algorithms for increasing transmission through highly-scattering random media using phase-only modulated wavefronts

Recent theoretical and experimental advances have shed light on the existence of so-called `perfectly transmitting' wavefronts with transmission coefficients close to 1 in strongly backscattering random media. These perfectly transmitting eigen-wavefronts can be synthesized by spatial amplitude and phase modulation. Here, we consider the problem of transmission enhancement using phase-only modulated wavefronts. We develop physically realizable iterative and non-iterative algorithms for increasing the transmission through such random media using backscatter analysis. We theoretically show that, despite the phase-only modulation constraint, the non-iterative algorithms will achieve at least about 25$π$% or about 78.5% transmission assuming there is at least one perfectly transmitting eigen-wavefront and that the singular vectors of the transmission matrix obey a maximum entropy principle so that they are isotropically random. We numerically analyze the limits of phase-only modulated transmission in 2-D with fully spectrally accurate simulators and provide rigorous numerical evidence confirming our theoretical prediction in random media with periodic boundary conditions that is composed of hundreds of thousands of non-absorbing scatterers. We show via numerical simulations that the iterative algorithms we have developed converge rapidly, yielding highly transmitting wavefronts using relatively few measurements of the backscatter field. Specifically, the best performing iterative algorithm yields approx 70% transmission using just 15-20 measurements in the regime where the non-iterative algorithms yield approximately 78.5% transmission but require measuring the entire modal reflection matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Batch latency analysis and phase transitions for a tandem of queues with exponentially distributed service times

We analyze the latency or sojourn time L(m,n) for the last customer in a batch of n customers to exit from the m-th queue in a tandem of m queues in the setting where the queues are in equilibrium before the batch of customers arrives at the first queue. We first characterize the distribution of L(m,n) exactly for every m and n, under the assumption that the queues have unlimited buffers and that each server has customer independent, exponentially distributed service times with an arbitrary, known rate. We then evaluate the first two leading order terms of the distributions in the large m and n limit and bring into sharp focus the existence of phase transitions in the system behavior. The phase transition occurs due to the presence of either slow bottleneck servers or a high external arrival rate. We determine the critical thresholds for the service rate and the arrival rate, respectively, about which this phase transition occurs; it turns out that they are the same. This critical threshold depends, in a manner we make explicit, on the individual service rates, the number of customers and the number of queues but not on the external arrival rate.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Iterative, backscatter-analysis algorithms for increasing transmission and focusing light through highly-scattering random media

Scattering hinders the passage of light through random media and consequently limits the usefulness of optical techniques for sensing and imaging. Thus, methods for increasing the transmission of light through such random media are of interest. Against this backdrop, recent theoretical and experimental advances have suggested the existence of a few highly transmitting eigen-wavefronts with transmission coefficients close to one in strongly backscattering random media. Here, we numerically analyze this phenomenon in 2-D with fully spectrally accurate simulators and provide rigorous numerical evidence confirming the existence of these highly transmitting eigen-wavefronts in random media with periodic boundary conditions that is composed of hundreds of thousands of non-absorbing scatterers. Motivated by bio-imaging applications where it is not possible to measure the transmitted fields, we develop physically realizable algorithms for increasing the transmission through such random media using backscatter analysis. We show via numerical simulations that the algorithms converge rapidly, yielding a near-optimum wavefront in just a few iterations. We also develop an algorithm that combines the knowledge of these highly transmitting eigen-wavefronts obtained from backscatter analysis, with intensity measurements at a point to produce a near-optimal focus with significantly fewer measurements than a method that does not utilize this information.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

OptShrink: An algorithm for improved low-rank signal matrix denoising by optimal, data-driven singular value shrinkage

The truncated singular value decomposition (SVD) of the measurement matrix is the optimal solution to the_representation_ problem of how to best approximate a noisy measurement matrix using a low-rank matrix. Here, we consider the (unobservable)_denoising_ problem of how to best approximate a low-rank signal matrix buried in noise by optimal (re)weighting of the singular vectors of the measurement matrix. We exploit recent results from random matrix theory to exactly characterize the large matrix limit of the optimal weighting coefficients and show that they can be computed directly from data for a large class of noise models that includes the i.i.d. Gaussian noise case. Our analysis brings into sharp focus the shrinkage-and-thresholding form of the optimal weights, the non-convex nature of the associated shrinkage function (on the singular values) and explains why matrix regularization via singular value thresholding with convex penalty functions (such as the nuclear norm) will always be suboptimal. We validate our theoretical predictions with numerical simulations, develop an implementable algorithm (OptShrink) that realizes the predicted performance gains and show how our methods can be used to improve estimation in the setting where the measured matrix has missing entries.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Sampling unitary invariant ensembles

We develop an algorithm for sampling from the unitary invariant random matrix ensembles. The algorithm is based on the representation of their eigenvalues as a determinantal point process whose kernel is given in terms of orthogonal polynomials. Using this algorithm, statistics beyond those known through analysis are calculable through Monte Carlo simulation. Unexpected phenomena are observed in the simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Local Spectrum of Truncations of Kronecker Products of Haar Distributed Unitary Matrices

We address the local spectral behavior of the random matrix $Π_1 U^{\otimes k} Π_2 U^{\otimes k *} Π_1$, where $U$ is a Haar distributed unitary matrix of size $n\times n$, the factor $k$ is at most $c_0\log n$ for a small constant $c_0>0$, and $Π_1,Π_2$ are arbitrary projections on $\ell_2^{n^k}$ of ranks proportional to $n^k$. We prove that in this setting the $k$-fold Kronecker product behaves similarly to the well-studied case when $k=1$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Numerical computation of convolutions in free probability theory

We develop a numerical approach for computing the additive, multiplicative and compressive convolution operations from free probability theory. We utilize the regularity properties of free convolution to identify (pairs of) `admissible' measures whose convolution results in a so-called `invertible measure' which is either a smoothly-decaying measure supported on the entire real line (such as the Gaussian) or square-root decaying measure supported on a compact interval (such as the semi-circle). This class of measures is important because these measures along with their Cauchy transforms can be accurately represented via a Fourier or Chebyshev series expansion, respectively. Thus, knowledge of the functional inverse of their Cauchy transform suffices for numerically recovering the invertible measure via a non-standard yet well-behaved Vandermonde system of equations. We describe explicit algorithms for computing the inverse Cauchy transform alluded to and recovering the associated measure with spectral accuracy. Convergence is guaranteed under broad assumptions on the input measures.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Spectra of random graphs with community structure and arbitrary degrees

Using methods from random matrix theory researchers have recently calculated the full spectra of random networks with arbitrary degrees and with community structure. Both reveal interesting spectral features, including deviations from the Wigner semicircle distribution and phase transitions in the spectra of community structured networks. In this paper we generalize both calculations, giving a prescription for calculating the spectrum of a network with both community structure and an arbitrary degree distribution. In general the spectrum has two parts, a continuous spectral band, which can depart strongly from the classic semicircle form, and a set of outlying eigenvalues that indicate the presence of communities.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

When are the most informative components for inference also the principal components?

Which components of the singular value decomposition of a signal-plus-noise data matrix are most informative for the inferential task of detecting or estimating an embedded low-rank signal matrix? Principal component analysis ascribes greater importance to the components that capture the greatest variation, i.e., the singular vectors associated with the largest singular values. This choice is often justified by invoking the Eckart-Young theorem even though that work addresses the problem of how to best represent a signal-plus-noise matrix using a low-rank approximation and not how to best_infer_ the underlying low-rank signal component. Here we take a first-principles approach in which we start with a signal-plus-noise data matrix and show how the spectrum of the noise-only component governs whether the principal or the middle components of the singular value decomposition of the data matrix will be the informative components for inference. Simply put, if the noise spectrum is supported on a connected interval, in a sense we make precise, then the use of the principal components is justified. When the noise spectrum is supported on multiple intervals, then the middle components might be more informative than the principal components. The end result is a proper justification of the use of principal components in the setting where the noise matrix is i.i.d. Gaussian and the identification of scenarios, generically involving heterogeneous noise models such as mixtures of Gaussians, where the middle components might be more informative than the principal components so that they may be exploited to extract additional processing gain. Our results show how the blind use of principal components can lead to suboptimal or even faulty inference because of phase transitions that separate a regime where the principal components are informative from a regime where they are uninformative.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Graph spectra and the detectability of community structure in networks

We study networks that display community structure -- groups of nodes within which connections are unusually dense. Using methods from random matrix theory, we calculate the spectra of such networks in the limit of large size, and hence demonstrate the presence of a phase transition in matrix methods for community detection, such as the popular modularity maximization method. The transition separates a regime in which such methods successfully detect the community structure from one in which the structure is present but is not detected. By comparing these results with recent analyses of maximum-likelihood methods we are able to show that spectral modularity maximization is an optimal detection method in the sense that no other method will succeed in the regime where the modularity method fails.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Spectra of random graphs with arbitrary expected degrees

We study random graphs with arbitrary distributions of expected degree and derive expressions for the spectra of their adjacency and modularity matrices. We give a complete prescription for calculating the spectra that is exact in the limit of large network size and large vertex degrees. We also study the effect on the spectra of hubs in the network, vertices of unusually high degree, and show that these produce isolated eigenvalues outside the main spectral band, akin to impurity states in condensed matter systems, with accompanying eigenvectors that are strongly localized around the hubs. We also give numerical results that confirm our analytic expressions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The singular values and vectors of low rank perturbations of large rectangular random matrices

In this paper, we consider the singular values and singular vectors of finite, low rank perturbations of large rectangular random matrices. Specifically, we prove almost sure convergence of the extreme singular values and appropriate projections of the corresponding singular vectors of the perturbed matrix. As in the prequel, where we considered the eigenvalue aspect of the problem, the non-random limiting value is shown to depend explicitly on the limiting singular value distribution of the unperturbed matrix via an integral transforms that linearizes rectangular additive convolution in free probability theory. The large matrix limit of the extreme singular values of the perturbed matrix differs from that of the original matrix if and only if the singular values of the perturbing matrix are above a certain critical threshold which depends on this same aforementioned integral transform. We examine the consequence of this singular value phase transition on the associated left and right singular eigenvectors and discuss the finite $n$ fluctuations above these non-random limits.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices

We consider the eigenvalues and eigenvectors of finite, low rank perturbations of random matrices. Specifically, we prove almost sure convergence of the extreme eigenvalues and appropriate projections of the corresponding eigenvectors of the perturbed matrix for additive and multiplicative perturbation models. The limiting non-random value is shown to depend explicitly on the limiting eigenvalue distribution of the unperturbed random matrix and the assumed perturbation model via integral transforms that correspond to very well known objects in free probability theory that linearize non-commutative free additive and multiplicative convolution. Furthermore, we uncover a phase transition phenomenon whereby the large matrix limit of the extreme eigenvalues of the perturbed matrix differs from that of the original matrix if and only if the eigenvalues of the perturbing matrix are above a certain critical threshold. Square root decay of the eigenvalue density at the edge is sufficient to ensure that this threshold is finite. This critical threshold is intimately related to the same aforementioned integral transforms and our proof techniques bring this connection and the origin of the phase transition into focus. Consequently, our results extend the class of `spiked' random matrix models about which such predictions (called the BBP phase transition) can be made well beyond the Wigner, Wishart and Jacobi random ensembles found in the literature. We examine the impact of this eigenvalue phase transition on the associated eigenvectors and observe an analogous phase transition in the eigenvectors. Various extensions of our results to the problem of non-extreme eigenvalues are discussed.

0 citations0 reviewsNo code linkedOpen access