Recent developments in the spectral theory of Bayesian Networks has led to a need for a developed theory of estimation and inference on the eigenvalues of the normalized precision matrix, . In this paper, working under conditions where and remains fixed, we provide multivariate normal asymptotic distributions of the sample eigenvalues of under general conditions and under normal populations, a formula for second-order bias correction of these sample eigenvalues, and a Stein-type shrinkage estimator of the eigenvalues. Numerical simulations are performed which demonstrate under what generative conditions each estimation technique is most effective. When the largest eigenvalue of is small the simulations show that the second order bias-corrected eigenvalue was considerably less biased than the sample eigenvalue, whereas the smallest eigenvalue was estimated with less bias using either the sample eigenvalue or the proposed shrinkage method.

Let be a tree on vertices and let denote the Laplacian matrix on . The second-smallest eigenvalue , also known as the algebraic connectivity, as well as the associated eigenvector have been of substantial interest. We investigate the question of when the maxima and minima of an associated eigenvector are assumed at the endpoints of the longest path in . Our results also apply to more general graphs that 'behave globally' like a tree but can exhibit more complicated local structure. The crucial new ingredient is a reproducing formula for eigenvectors of graphs.

A Bayesian Network (BN) is a probabilistic model that represents a set of variables using a directed acyclic graph (DAG). Current algorithms for learning BN structures from data focus on estimating the edges of a specific DAG, and often lead to many 'likely' network structures. In this paper, we lay the groundwork for an approach that focuses on learning global properties of the DAG rather than exact edges. This is done by defining the of a BN, which is shown to be related to the inverse-covariance matrix of the network. Spectral bounds are derived for the normalized inverse-covariance matrix, which are shown to be closely related to the maximum indegree of the associated BN.

A binary tensor consists of 2 entries arranged into hypercube format 2 × 2 × ⋯ × 2. There are ways to flatten such a tensor into a matrix of size 2 × 2 . For each flattening, , we take the determinant of its Gram matrix, det( ). We consider the map that sends a tensor to its -tuple of Gram determinants. We propose a semi-algebraic characterization of the image of this map. This offers an answer to a question raised by Hackbusch and Uschmajew concerning the higher-order singular values of tensors.

Motivated by a certain molecular reconstruction methodology in cryo-electron microscopy, we consider the problem of solving a linear system with two unknown orthogonal matrices, which is a generalization of the well-known orthogonal Procrustes problem. We propose an algorithm based on a semi-definite programming (SDP) relaxation, and give a theoretical guarantee for its performance. Both theoretically and empirically, the proposed algorithm performs better than the naïve approach of solving the linear system directly without the orthogonal constraints. We also consider the generalization to linear systems with more than two unknown orthogonal matrices.

Interest in higher-order tensors has recently surged in data-intensive fields, with a wide range of applications including image processing, blind source separation, community detection, and feature extraction. A common paradigm in tensor-related algorithms advocates unfolding (or flattening) the tensor into a matrix and applying classical methods developed for matrices. Despite the popularity of such techniques, how the functional properties of a tensor changes upon unfolding is currently not well understood. In contrast to the body of existing work which has focused almost exclusively on matricizations, we here consider all possible unfoldings of an order- tensor, which are in one-to-one correspondence with the set of partitions of {1, …, }. We derive general inequalities between the -norms of arbitrary unfoldings defined on the partition lattice. In particular, we demonstrate how the spectral norm ( = 2) of a tensor is bounded by that of its unfoldings, and obtain an improved upper bound on the ratio of the Frobenius norm to the spectral norm of an arbitrary tensor. For specially-structured tensors satisfying a generalized definition of orthogonal decomposability, we prove that the spectral norm remains invariant under specific subsets of unfolding operations.

We address two sets of long-standing open questions in linear algebra and probability theory, from a computational complexity perspective: stochastic matrix divisibility, and divisibility and decomposability of probability distributions. We prove that finite divisibility of stochastic matrices is an NP-complete problem, and extend this result to nonnegative matrices, and completely-positive trace-preserving maps, i.e. the quantum analogue of stochastic matrices. We further prove a complexity hierarchy for the divisibility and decomposability of probability distributions, showing that finite distribution divisibility is in P, but decomposability is NP-hard. For the former, we give an explicit polynomial-time algorithm. All results on distributions extend to weak-membership formulations, proving that the complexity of these problems is robust to perturbations.

We describe a new method to compute general cubature formulae. The problem is initially transformed into the computation of truncated Hankel operators with flat extensions. We then analyze the algebraic properties associated to flat extensions and show how to recover the cubature points and weights from the truncated Hankel operator. We next present an algorithm to test the flat extension property and to additionally compute the decomposition. To generate cubature formulae with a minimal number of points, we propose a new relaxation hierarchy of convex optimization problems minimizing the nuclear norm of the Hankel operators. For a suitably high order of convex relaxation, the minimizer of the optimization problem corresponds to a cubature formula. Furthermore cubature formulae with a minimal number of points are associated to faces of the convex sets. We illustrate our method on some examples, and for each we obtain a new minimal cubature formula.

We develop statistical methodology for a popular brain imaging technique HARDI based on the high order tensor model by Özarslan and Mareci [10]. We investigate how uncertainty in the imaging procedure propagates through all levels of the model: signals, tensor fields, vector fields, and fibers. We construct asymptotically normal estimators of the integral curves or fibers which allow us to trace the fibers together with confidence ellipsoids. The procedure is computationally intense as it blends linear algebra concepts from high order tensors with asymptotical statistical analysis. The theoretical results are illustrated on simulated and real datasets. This work generalizes the statistical methodology proposed for low angular resolution diffusion tensor imaging by Carmichael and Sakhanenko [3], to several fibers per voxel. It is also a pioneering statistical work on tractography from HARDI data. It avoids all the typical limitations of the deterministic tractography methods and it delivers the same information as probabilistic tractography methods. Our method is computationally cheap and it provides well-founded mathematical and statistical framework where diverse functionals on fibers, directions and tensors can be studied in a systematic and rigorous way.

The literature is replete with rich connections between the structure of a graph G = (V, E) and the spectral properties of its Laplacian matrix L. This paper establishes similar connections between the structure of G and the Laplacian L* of a second graph G*. Our interest lies in L* that can be obtained from L by Schur complementation, in which case we say that G* is partially-supplied with respect to G. In particular, we specialize to where G is a tree with points of articulation r ∈ R and consider the partially-supplied graph G* derived from G by taking the Schur complement with respect to R in L. Our results characterize how the eigenvectors of the Laplacian of G* relate to each other and to the structure of the tree.

We show how to construct an eigenvector basis of the discrete Fourier transform of odd prime order. The special feature of the new basis is that the basis vectors have small support.

Control design belongs to the most important and difficult tasks of control engineering and has therefore been treated by many prominent researchers and in many textbooks, the systems being generally described by their transfer matrices or by Rosenbrock equations and more recently also as behaviors. Our approach to controller design uses, in addition to the ideas of our predecessors on coprime factorizations of transfer matrices and on the parametrization of stabilizing compensators, a new mathematical technique which enables simpler design and also new theorems in spite of the many outstanding results of the literature: (1) We use an injective cogenerator signal module ℱ over the polynomial algebra [Formula: see text] (F an infinite field), a saturated multiplicatively closed set T of stable polynomials and its quotient ring [Formula: see text] of stable rational functions. This enables the simultaneous treatment of continuous and discrete systems and of all notions of stability, called T-stability. We investigate stabilizing control design by output feedback of input/output (IO) behaviors and study the full feedback IO behavior, especially its autonomous part and not only its transfer matrix. (2) The new technique is characterized by the permanent application of the injective cogenerator quotient signal module [Formula: see text] and of quotient behaviors [Formula: see text] of [Formula: see text]-behaviors B. (3) For the control tasks of tracking, disturbance rejection, model matching, and decoupling and not necessarily proper plants we derive necessary and sufficient conditions for the existence of proper stabilizing compensators with proper and stable closed loop behaviors, parametrize all such compensators as IO behaviors and not only their transfer matrices and give new algorithms for their construction. Moreover we solve the problem of pole placement or spectral assignability for the complete feedback behavior. The properness of the full feedback behavior ensures the absence of impulsive solutions in the continuous case, and that of the compensator enables its realization by Kalman state space equations or elementary building blocks. We note that every behavior admits an IO decomposition with proper transfer matrix, but that most of these decompositions do not have this property, and therefore we do not assume the properness of the plant. (4) The new technique can also be applied to more general control interconnections according to Willems, in particular to two-parameter feedback compensators and to the recent tracking framework of Fiaz/Takaba/Trentelman. In contrast to these authors, however, we pay special attention to the properness of all constructed transfer matrices which requires more subtle algorithms.

Let G be a simple graph of order n and A(G) be its adjacency matrix. The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in the spectrum of A(G). Denote by Ck and Lk the set of all connected graphs with k induced cycles and the set of line graphs of all graphs in Ck, respectively. In 1998, Sciriha [I. Sciriha, On singular line graphs of trees, Congr. Numer. 135 (1998) 73-91] show that the order of every tree whose line graph is singular is even. Then Gutman and Sciriha [I. Gutman, I. Sciriha, On the nullity of line graphs of trees, Discrete Math. 232 (2001) 35-45] show that the nullity set of L0 is {0,1}. In this paper, we investigate the nullity of graphs with cut-points and deduce some concise formulas. Then we generalize Scirihas' result, showing that the order of every graph G is even if such a graph G satisfies that G∈Ck and η(L(G))=k+1, and the nullity set of Lk is {0,1,…,k,k+1} for any given k, where L(G) denotes the line graph of the graph G.

We obtain the lower bound on a variant of the common problem of dimensionality reduction. In this version, the dataset is projected on to a k dimensional subspace with the property that the first k-1 basis vectors are fixed, leaving a single degree of freedom in terms of basis vectors.

The least squares solution of a complex linear equation is in general a complex vector with independent real and imaginary parts. In certain applications in magnetic resonance imaging, a solution is desired such that each element has the same phase. A direct method for obtaining the least squares solution to the phase constrained problem is described.

The Euclidean distance matrix for distinct points in ℝ is generically of rank + 2. It is shown in this paper via a geometric argument that its nonnegative rank for the case = 1 is generically .

The utility of Fiedler vectors in interrogating the structure of graphs has generated intense interest and motivated the pursuit of further theoretical results. This paper focuses on how the Fiedler vectors of one graph reveal structure in a second graph that is related to the first. Specifically, we consider a point of articulation in the graph whose Laplacian matrix is and derive a related graph whose Laplacian is the matrix obtained by taking the Schur complement with respect to in . We show how Fiedler vectors of relate to the structure of and we provide bounds for the algebraic connectivity of in terms of the connected components at in . In the case where is a tree with points of articulation ∈ , we further consider the graph derived from by taking the Schur complement with respect to in . We show that Fiedler vectors of valuate the pendent vertices of in a manner consistent with the structure of the tree.

The goal of Intensity-Modulated Radiation Therapy (IMRT) is to deliver sufficient doses to tumors to kill them, but without causing irreparable damage to critical organs. This requirement can be formulated as a linear feasibility problem. The sequential (i.e., iteratively treating the constraints one after another in a cyclic fashion) algorithm ART3 is known to find a solution to such problems in a finite number of steps, provided that the feasible region is full dimensional. We present a faster algorithm called ART3+. The idea of ART3+ is to avoid unnecessary checks on constraints that are likely to be satisfied. The superior performance of the new algorithm is demonstrated by mathematical experiments inspired by the IMRT application.

Treatment planning for intensity modulated radiation therapy (IMRT) is challenging due to both the size of the computational problems (thousands of variables and constraints) and the multi-objective, imprecise nature of the goals. We apply hierarchical programming to IMRT treatment planning. In this formulation, treatment planning goals/objectives are ordered in an absolute hierarchy, and the problem is solved from the top-down such that more important goals are optimized in turn. After each objective is optimized, that objective function is converted into a constraint when optimizing lower-priority objectives. We also demonstrate the usefulness of a linear/quadratic formulation, including the use of mean-tail-dose (mean dose to the hottest fraction of a given structure), to facilitate computational efficiency. In contrast to the conventional use of dose-volume constraints (no more than x% volume of a structure should receive more than y dose), the mean-tail-dose formulation ensures convex feasibility spaces and convex objective functions. To widen the search space without seriously degrading higher priority goals, we allowed higher priority constraints to relax or 'slip' a clinically negligible amount during lower priority iterations. This method was developed and tuned for external beam prostate planning and subsequently tested using a suite of 10 patient datasets. In all cases, good dose distributions were generated without individual plan parameter adjustments. It was found that allowance for a small amount of 'slip,' especially in target dose homogeneity, often resulted in improved normal tissue dose burdens. Compared to the conventional IMRT treatment planning objective function formulation using a weighted linear sum of terms representing very different dosimetric goals, this method: (1) is completely automatic, requiring no user intervention, (2) ensures high-priority planning goals are not seriously degraded by lower-priority goals, and (3) ensures that lower priority, yet still important, normal tissue goals are separately pushed as far as possible without seriously impacting higher priority goals.

It is commonly believed that not all degrees of freedom are needed to produce good solutions for the treatment planning problem in intensity modulated radiation therapy (IMRT). However, typical methods to exploit this fact either increase the complexity of the optimization problem or are heuristic in nature. In this work we introduce a technique based on adaptively refining variable clusters to successively attain better treatment plans. The approach creates approximate solutions based on smaller models that may come arbitrarily close to the optimal solution. Although the method is illustrated using a specific treatment planning model, the components constituting the variable clustering and the adaptive refinement are independent of the particular optimization problem.

The purpose of this paper is to describe certain alternative metrics for quantifying distances between distributions, and to explain their use and relevance in visual tracking. Besides the theoretical interest, such metrics may be used to design filters for image segmentation, that is for solving the key visual task of separating an object from the background in an image. The segmenting curve is represented as the zero level set of a signed distance function. Most existing methods in the geometric active contour framework perform segmentation by maximizing the separation of intensity moments between the interior and the exterior of an evolving contour. Here one can use the given distributional metric to determine a flow which minimizes changes in the distribution inside and outside the curve.