Minimum Spanning vs. Principal Trees for Structured Approximations of Multi-Dimensional Datasets

Construction of graph-based approximations for multi-dimensional data point clouds is widely used in a variety of areas. Notable examples of applications of such approximators are cellular trajectory inference in single-cell data analysis, analysis of clinical trajectories from synchronic datasets, and skeletonization of images. Several methods have been proposed to construct such approximating graphs, with some based on computation of minimum spanning trees and some based on principal graphs generalizing principal curves. In this article we propose a methodology to compare and benchmark these two graph-based data approximation approaches, as well as to define their hyperparameters. The main idea is to avoid comparing graphs directly, but at first to induce clustering of the data point cloud from the graph approximation and, secondly, to use well-established methods to compare and score the data cloud partitioning induced by the graphs. In particular, mutual information-based approaches prove to be useful in this context. The induced clustering is based on decomposing a graph into non-branching segments, and then clustering the data point cloud by the nearest segment. Such a method allows efficient comparison of graph-based data approximations of arbitrary topology and complexity. The method is implemented in Python using the standard scikit-learn library which provides high speed and efficiency. As a demonstration of the methodology we analyse and compare graph-based data approximation methods using synthetic as well as real-life single cell datasets.     

Heterogeneous Graphical Granger Causality by Minimum Message Length

The heterogeneous graphical Granger model (HGGM) for causal inference among processes with distributions from an exponential family is efficient in scenarios when the number of time observations is much greater than the number of time series, normally by several orders of magnitude. However, in the case of “short” time series, the inference in HGGM often suffers from overestimation. To remedy this, we use the minimum message length principle (MML) to determinate the causal connections in the HGGM. The minimum message length as a Bayesian information-theoretic method for statistical model selection applies Occam’s razor in the following way: even when models are equal in their measure of fit-accuracy to the observed data, the one generating the most concise explanation of data is more likely to be correct. Based on the dispersion coefficient of the target time series and on the initial maximum likelihood estimates of the regression coefficients, we propose a minimum message length criterion to select the subset of causally connected time series with each target time series and derive its form for various exponential distributions. We propose two algorithms—the genetic-type algorithm (HMMLGA) and exHMML to find the subset. We demonstrated the superiority of both algorithms in synthetic experiments with respect to the comparison methods Lingam, HGGM and statistical framework Granger causality (SFGC). In the real data experiments, we used the methods to discriminate between pregnancy and labor phase using electrohysterogram data of Islandic mothers from Physionet databasis. We further analysed the Austrian climatological time measurements and their temporal interactions in rain and sunny days scenarios. In both experiments, the results of HMMLGA had the most realistic interpretation with respect to the comparison methods. We provide our code in Matlab. To our best knowledge, this is the first work using the MML principle for causal inference in HGGM.     

混合图上最小-最大圈覆盖问题的近似算法

考虑一个混合图上的最小-最大圈覆盖问题.给定一个正整数k和一个混合加权图G=(V E,A),这里V表示顶点集,E表示边集,A表示弧集.E中的每条边和A中的每条弧关联一个权重.问题的要求是确定k个环游,使得这k个环游能够经过A中的所有弧.目标是极小化最大环游的权重.该问题是运筹学和计算机科学中一个重要的组合优化问题,它和...     

球状物体作微形变时弹性势能的研究

研究一个弹性球在保持体积不变的前提下,形变为长旋转椭球时的弹性势能.首先通过最小势能原理和物理条件确定位移函数,然后根据弹性势能密度-应变-位移三者之间的关系,通过积分计算得到弹性势能,并且进行了有益的讨论.     

一种新型的两态叠加MSCS光场的广义非线性等阶N次方H压缩

本文利用新近建立的多模压缩态理论,详细研究了一种新型的两态叠加多模薛定谔猫态(即MSCS)光场|ψ⁽²⁾〉_q的广义非线性等阶N次方H压缩效应.结果发现:1态|ψ⁽²⁾〉_q是一种典型的非经典光场;当压缩阶数N与腔模总数q这两者之积为偶数,即qN=2p,并且p为奇数亦即p=2m’+1(m’=0,1,2,3,…,…)时,如果各模的初始相位和∑_j=1^qψ_j态间的初始相位差(θ_pq^(I)-θ_nq^(R))、各多模相干态光场的总的平均光子数∑_j=1^qR_j²等满足一定的量子化条件(或者当∑_j=1^qR_j²在总的平均光子数∑_j=1^qR_j²的一系列压缩区内连续取值时),态|ψ(2)〉q总可呈现出周期性变化的、任意阶的广义非线性等阶N次方H压缩效应.2态|ψ⁽²⁾〉_q的第一及第二两个正交分量,其压缩结果(亦即压缩程度和压缩深度)完全相同,但压缩条件不同;两者的等阶N次方H压缩效应呈现出周期性的互补关系.3与文献16相比,本文所研究的态|ψ⁽²⁾〉_q的等阶N次方H压缩效应是比其等阶N次方Y压缩效应更高阶的广义非线性等阶高阶压缩效应.     

多模复共轭虚奇相干态光场的等阶高次压缩特性研究

本文构造了一种新型的多模复共轭虚奇相干态光场|Ψ_i,o^*(2)>_q,利用多模压缩态理论详细研究了态|Ψ_i,o^*(2)>_q的等阶N次方Y压缩与等阶N次方H压缩特性.结果发现:与多模奇相干态光场、多模复共轭奇相干态光场和多模虚奇相干态光场等所有的多纵模奇相干态光场的性质相同,多模复共轭虚奇相干态光场在任何条件下都不呈现等阶N次方Y压缩效应与等阶N次方H压缩效应,但在一定条件下却可恒处于等阶N-Y最小测不准态和等阶N-H最小测不准态.这表明所有的多纵模奇相干态光场之间,必定存在某些内在的必然性联系.     

Structural Dependence of Electronic and Magnetic Properties of the Cr13 Cluster

A tight-binding effective potential has been employed, in conjunction with a genetic algorithm, to fully optimize the Cr₁₃ cluster geometry without imposing any symmetry constraints. The minimum energy structure of this cluster is found to be a slightly distorted icosahedron. Based on the optimized structure and three assumed geometries (icosahedron,bcc-like and fcc-like), the structural dependence of electronic and magnetic properties of the Cr₁₃ cluster is discussed by using a d-band Hubbard-like Hamiltonian in the unrestricted Hartree-Fock approximation. Results are given for the average magnetic moment and local magnetic moments. It is found that for all considered geometries the Cr₁₃ cluster exhibits antiferromagnetic behavior. Results are also given for the cohesive energy, average coordination number, and local electronic densities of states. The results indicate that the average coordination number per atom in the cluster geometry is a significant factor to affect the magnetism.Also, the local density of states is a sensitive function of geometry.     

Operational Variants of the Minimum Mean Squared Error Estimator in Linear Regression Models with Non-Spherical Disturbances

There is a good deal of literature that investigates the properties of various operational variants of Theil's (1971, Principles of Econometrics, Wiley, New York) minimum mean squared error estimator. It is interesting that virtually all of the existing analysis to date is based on the premise that the model's disturbances are i.i.d., an assumption which is not satisfied in many practical situations. In this paper, we consider a model with non-spherical errors and derive the asymptotic distribution, bias and mean squared error of a general class of feasible minimum mean squared error estimators. A Monte-Carlo experiment is conducted to examine the performance of this class of estimators in finite samples.     

Strong Embeddings of Outer Planar Near-triangulations on Non-orientable Surfaces

§ 1.Ｉｎｔｒｏｄｕｃｔｉｏｎ　ＦｏｒａｇｒａｐｈＧｗｅｄｅｎｏｔｅｂｙＶ(Ｇ)ａｎｄＥ(Ｇ) ,ｒｅｓｐｅｃｔｉｖｅｌｙ ,ｔｈｅｖｅｒｔｅｘｓｅｔａｎｄｅｄｇｅｓｅｔｏｆＧ ,ｗｉｔｈ |Ｖ(Ｇ) | =ν(Ｇ)ａｎｄ |Ｅ(Ｇ) | =ε(Ｇ) .Ａｇｒａｐｈｗｉｔｈｍｕｌｔｉ ｅｄｇｅａｌｌｏｗａｂｌｅｉｓｃａｌｌｅｄａｍｕｌｔｉ ｇｒａｐｈ .Ａｐｌａｎａｒｇｒａｐｈｉｓｓｕｃｈａｇｒａｐｈｗｈｉｃｈｈａｓａｎｅｍｂｅｄｄｉｎｇ μ(Ｇ)ｏｆｔｈｅｇｒａｐｈｉｎｔｈｅｐｌａｎｅ .ＩｆＧｉｓａｐｌａｎａｒｇｒａｐｈ ,ｗｅｄｅｎ…     

The Sequence-covering Compact Images of Paracompact Locally Compact Spaces

Ｉｎｔｈｉｓｐａｐｅｒ,ａｌｌｓｐａｃｅｓａｒｅｒｅｇｕｌａｒａｎｄＴ1,ａｎｄａｌｌｍａｐｐｉｎｇｓａｒｅｃｏｎｔｉｎｕｏｕｓａｎｄｏｎｔｏ .Ｒｅａｄｅｒｓｍａｙｒｅｆｅｒｔｏ [1 ]ｆｏｒｕｎｓｔａｔｅｄｄｅｆｉｎｉｔｉｏｎｓ.　Ｑｕｉｔｅｒｅｃｅｎｔｌｙ ,ｓｏｍｅｃｈａｒａｃｔｅｒｉｚａｔｉｏｎｓｆｏｒｃｅｒｔａｉｎＬ ｉｍａｇｅｓｏｆｐａｒａｃｏｍｐａｃｔｌｏｃａｌｌｙｃｏｍｐａｃｔｓｐａｃｅｓｈａｖｅｂｅｅｎｏｂｔａｉｎｅｄｉｎ [2 ] .Ｓｉｍｉｌａｒｌｙ ,ｗｅｃａｎｅｓｔａｂｌｉｓｈｔｈｅｃｈ…