Search

The cornerstone of stroke care is expedient management that varies depending on the time since stroke onset. Consequently, clinical decision making is centered on accurate knowledge of timing and often requires a radiologist to interpret Computed Tomography (CT) of the brain to confirm the occurrence and age of an event. These tasks are particularly challenging due to the subtle expression of acute ischemic lesions and the dynamic nature of their appearance. Automation efforts have not yet applied deep learning to estimate lesion age and treated these two tasks independently, so, have overlooked their inherent complementary relationship. To leverage this, we propose a novel end-to-end multi-task transformer-based network optimized for concurrent segmentation and age estimation of cerebral ischemic lesions. By utilizing gated positional self-attention and CT-specific data augmentation, the proposed method can capture long-range spatial dependencies while maintaining its ability to be trained from scratch under low-data regimes commonly found in medical imaging. Furthermore, to better combine multiple predictions, we incorporate uncertainty by utilizing quantile loss to facilitate estimating a probability density function of lesion age. The effectiveness of our model is then extensively evaluated on a clinical dataset consisting of 776 CT images from two medical centers. Experimental results demonstrate that our method obtains promising performance, with an area under the curve (AUC) of 0.933 for classifying lesion ages <=4.5 hours compared to 0.858 using a conventional approach, and outperforms task-specific state-of-the-art algorithms.

We use techniques from finite free probability to analyze matrix processes related to eigenvalues, singular values, and generalized singular values of random matrices. The models we use are quite basic and the analysis consists entirely of expected characteristic polynomials. A number of our results match known results in random matrix theory, however our main result (regarding generalized singular values) seems to be more general than any of the standard random matrix processes (Hermite/Laguerre/Jacobi) in the field. To test this, we perform a series of simulations of this new process that, on the one hand, confirms that this process can exhibit behavior not seen in the standard random matrix processes, but on the other hand provides evidence that the true behavior is captured quite well by our techniques. This, coupled with the fact that we are able to compute the same statistics for this new model that we are for the standard models, suggests that further investigation could be both interesting and fruitful.

We introduce a finite version of free probability and show the link between recent results using polynomial convolutions and the traditional theory of free probability. One tool for accomplishing this is a seemingly new transformation that allows one to reduce computations in our new theory to computations using classically independent random variables. We then explore the idea of finite freeness and its implications. Lastly, we show applications of the new theory by deriving the finite versions of some well-known free distributions and then proving their associated limit laws directly. In the process, we gain a number of insights into the behavior of convolutions in traditional free probability that seem to get lost when the operators being convolved are no longer finite. This version contains the original preprint from 2016 as well as an extra section (Section 5.2) where we use finite freeness to prove majorization relations on certain convolution.

We prove that there exist bipartite, biregular Ramanujan graphs of every degree and every number of vertices provided that the cardinalities of the two sets of the bipartition divide each other. This generalizes a result of Marcus, Spielman, and Srivastava and, similar to theirs, the proof is based on the analysis of expected polynomials. The primary difference is the use of some new machinery involving rectangular convolutions, developed in a companion paper. We also prove the constructibility of such graphs in polynomial time in the number of vertices, extending a result of Cohen to this biregular case.

We prove an identity relating the permanent of a rank $2$ matrix and the determinants of its Hadamard powers. When viewed in the right way, the resulting formula looks strikingly similar to an identity of Carlitz and Levine, suggesting the possibility that these are actually special cases of some more general identity (or class of identities) connecting permanents and determinants. The proof combines some basic facts from the theory of symmetric functions with an application of a famous theorem of Binet and Cauchy in linear algebra.

We prove two "master" convolution theorems for multivariate determinantal polynomials. The methods used include basic properties of what we call a "minor-orthogonal" ensemble as well as properties of the mixed discriminant of matrices. We also give applications, including a rederivation of a result of Barvinok on computing the permanent of a low rank matrix and a polynomial convolution corresponding to the unitarily invariant addition of generalized singular values.

We define the rectangular additive convolution of polynomials with nonnegative real roots as a generalization of the asymmetric additive convolution introduced by Marcus, Spielman and Srivastava. We then prove a sliding bound on the largest root of this convolution. The main tool used in the analysis is a differential operator derived from the "rectangular Cauchy transform" introduced by Benaych-Georges. The proof is inductive, with the base case requiring a new nonasymptotic bound on the Cauchy transform of Gegenbauer polynomials which may be of independent interest.

These lecture notes are meant to accompany two lectures given at the CDM 2016 conference, about the Kadison-Singer Problem. They are meant to complement the survey by the same authors (along with Spielman) which appeared at the 2014 ICM. In the first part of this survey we will introduce the Kadison-Singer problem from two perspectives ($C^*$ algebras and spectral graph theory) and present some examples showing where the difficulties in solving it lie. In the second part we will develop the framework of interlacing families of polynomials, and show how it is used to solve the problem. None of the results are new, but we have added annotations and examples which we hope are of pedagogical value.

We use the method of interlacing families of polynomials to derive a simple proof of Bourgain and Tzafriri's Restricted Invertibility Principle, and then to sharpen the result in two ways. We show that the stable rank can be replaced by the Schatten 4-norm stable rank and that tighter bounds hold when the number of columns in the matrix under consideration does not greatly exceed its number of rows. Our bounds are derived from an analysis of smallest zeros of Jacobi and associated Laguerre polynomials.

Three operations on eigenvalues of real/complex/quaternion (corresponding to $\beta=1,2,4$) matrices, obtained from cutting out principal corners, adding, and multiplying matrices can be extrapolated to general values of $\beta>0$ through associated special functions. We show that $\beta\to\infty$ limit for these operations leads to the finite free projection, additive convolution, and multiplicative convolution, respectively. The limit is the most transparent for cutting out the corners, where the joint distribution of the eigenvalues of principal corners of a uniformly-random general $\beta$ self-adjoint matrix with fixed eigenvalues is known as $\beta$-corners process. We show that as $\beta\to\infty$ these eigenvalues crystallize on the irregular lattice of all the roots of derivatives of a single polynomial. In the second order, we observe a version of the discrete Gaussian Free Field (dGFF) put on top of this lattice, which provides a new explanation of why the (continuous) Gaussian Free Field governs the global asymptotics of random matrix ensembles., Comment: 25 pages. v2: misprints corrected, to appear in IMRN

We show that certain determinantal functions of multiple matrices, when summed over the symmetries of the cube, decompose into functions of the original matrices. These are shown to be true in complete generality; that is, no properties of the underlying vector space will be used apart from normal ring properties, and therefore hold in any commutative ring. All proofs are elementary --- in fact, the majority are simply derivations.

We sharpen the constant in the $KS_2$ conjecture of Weaver \cite{We}, which was validated by Marcus, Spielman, and Srivastava \cite{MSS} in their solution of the Kadison--Singer problem. We then apply this result to prove optimal asymptotic bounds on the size of partitions in the Feichtinger conjecture.

We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices. The proof is based on analyzing the expected characteristic polynomial of a union of random perfect matchings, and involves three ingredients: (1) a formula for the expected characteristic polynomial of the sum of a regular graph with a random permutation of another regular graph, (2) a proof that this expected polynomial is real rooted and that the family of polynomials considered in this sum is an interlacing family, and (3) strong bounds on the roots of the expected characteristic polynomial of a union of random perfect matchings, established using the framework of finite free convolutions we recently introduced.

We study three convolutions of polynomials in the context of free probability theory. We prove that these convolutions can be written as the expected characteristic polynomials of sums and products of unitarily invariant random matrices. The symmetric additive and multiplicative convolutions were introduced by Walsh and Szeg\"o in different contexts, and have been studied for a century. The asymmetric additive convolution, and the connection of all of them with random matrices, is new. By developing the analogy with free probability, we prove that these convolutions produce real rooted polynomials and provide strong bounds on the locations of the roots of these polynomials.

We survey the techniques used in our recent resolution of the Kadison-Singer problem and proof of existence of Ramanujan Graphs of every degree: mixed characteristic polynomials and the method of interlacing families of polynomials. To demonstrate the method of interlacing families of polynomials, we give a simple proof of Bourgain and Tzafriri's restricted invertibility principle in the isotropic case., Comment: A version of this paper will appear in the proceedings of the 2014 International Congress of Mathematicians

We use the method of interlacing families of polynomials introduced to prove two theorems known to imply a positive solution to the Kadison--Singer problem. The first is Weaver's conjecture $KS_{2}$ \cite{weaver}, which is known to imply Kadison--Singer via a projection paving conjecture of Akemann and Anderson. The second is a formulation due to Casazza, et al., of Anderson's original paving conjecture(s), for which we are able to compute explicit paving bounds. The proof involves an analysis of the largest roots of a family of polynomials that we call the "mixed characteristic polynomials" of a collection of matrices., Comment: This is the version that has been submitted

We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph. We also establish the existence of infinite families of `irregular Ramanujan' graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we prove the existence of infinite families of (c,d)-biregular bipartite graphs with all non-trivial eigenvalues bounded by sqrt{c-1}+sqrt{d-1}, for all c, d \geq 3. Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "method of interlacing polynomials'".

Crowdsourcing markets like Amazon's Mechanical Turk (MTurk) make it possible to task people with small jobs, such as labeling images or looking up phone numbers, via a programmatic interface. MTurk tasks for processing datasets with humans are currently designed with significant reimplementation of common workflows and ad-hoc selection of parameters such as price to pay per task. We describe how we have integrated crowds into a declarative workflow engine called Qurk to reduce the burden on workflow designers. In this paper, we focus on how to use humans to compare items for sorting and joining data, two of the most common operations in DBMSs. We describe our basic query interface and the user interface of the tasks we post to MTurk. We also propose a number of optimizations, including task batching, replacing pairwise comparisons with numerical ratings, and pre-filtering tables before joining them, which dramatically reduce the overall cost of running sorts and joins on the crowd. In an experiment joining two sets of images, we reduce the overall cost from $67 in a naive implementation to about $3, without substantially affecting accuracy or latency. In an end-to-end experiment, we reduced cost by a factor of 14.5., Comment: VLDB2012

A new notion of partition-determined functions is introduced, and several basic inequalities are developed for the entropy of such functions of independent random variables, as well as for cardinalities of compound sets obtained using these functions. Here a compound set means a set obtained by varying each argument of a function of several variables over a set associated with that argument, where all the sets are subsets of an appropriate algebraic structure so that the function is well defined. On the one hand, the entropy inequalities developed for partition-determined functions imply entropic analogues of general inequalities of Pl\"unnecke-Ruzsa type. On the other hand, the cardinality inequalities developed for compound sets imply several inequalities for sumsets, including for instance a generalization of inequalities proved by Gyarmati, Matolcsi and Ruzsa (2010). We also provide partial progress towards a conjecture of Ruzsa (2007) for sumsets in nonabelian groups. All proofs are elementary and rely on properly developing certain information-theoretic inequalities., Comment: 26 pages. v2: Revised version incorporating referee feedback plus inclusion of some additional corollaries and discussion. v3: Final version with minor corrections. To appear in Random Structures and Algorithms

We present two extensions of the linear bound, due to Marcus and Tardos, on the number of 1's in an n by n 0-1 matrix avoiding a fixed permutation matrix. We first extend the linear bound to hypergraphs with ordered vertex sets and, using previous results of Klazar, we prove an exponential bound on the number of hypergraphs on n vertices which avoid a fixed permutation. This, in turn, solves various conjectures of Klazar as well as a conjecture of Branden and Mansour.We then extend the original Furedi-Hajnal problem from ordinary matrices to d-dimensional matrices and show that the number of 1's in a d-dimensional 0-1 matrix with side length n which avoids a d-dimensional permutation matrix is O(n^{d-1})., Comment: 11 pages