text:
Simulating p-value statistics for Liliefors test (Python statsmodels)

Python statsmodels has an implementation of Lilliefors' test for goodness of fit (i.e. if the parameters of the distribution were obtained from fitting the data and not per-determined as in the original Kolmogorov-Smirnow test). The implementation is based on tabulated p-value distributions from 10 mio simulations for different sample sizes and covers normal and exponential distributions. In Wilks' book "Statistical Methods in the Atmospheric Sciences" some tabulated values are provided for gamma distributions with different shape parameters.

I would like to re-create and extend these tables using the lilliefors_critical_value_simulation.pycode, which is provided in the statsmodels package. In principle, this is rather straightforward, but there is one step in the code, which is unclear to me, and this concerns z-normalisation of the random samples, which are drawn in each experiment. For the normal and exponential distributions, the code reads:

if sim_type == 'normal':
std = sample.std(0, ddof=1)
z = (sample - mu) / std
cdf_fn = stats.norm.cdf
elif sim_type == 'exponential':
z = sample / mu
cdf_fn = stats.expon.cdf

Indeed, scaling is pretty straightforward. However, for gamma distributions, a z-scale is not well defined (I also came across the term probability integral transform, but also this was limited to normal distributions). Upon research I found that people recommend to use quantiles instead of the standard deviation. I am now wondering, how critical the z-scaling is for the derivation of the p-value statistics, and if a pseudo z-scale (x - mu)/(75%-ile - 25%-ile) can be safely used in the context of simulating the p-value distribution.

Further information about the implementation details: The original source code of lilliefors_critical_value_simulation.py can be found at https://github.com/statsmodels/statsmodels/blob/master/statsmodels/stats/tests/results/lilliefors_critical_value_simulation.py. The relevant part begins in line 57, where the CDF of the z-normalized sample is calculated. Then, plus and minus are constructed as [1/N, ..., N/N] and [0, (N-1)/N], respectively and the differences plus-cdf and cdf-minus are evaluated. The result for this specific sample is then calculated as maximum absolute difference (concatenating d_plus and d_minus via the somewhat obstruse _csyntax; see https://numpy.org/doc/stable/reference/generated/numpy.c_.html). These results are collected for all sample sizes to be tabulated. Lateron (line 83 ff) the critical values are calculated by evaluating the precentiles of the results.

(Or has someone computed extensive tables for gamma distributions already and made them available somewhere?)

References:

How can one compute Lilliefors' test for arbitrary distributions?

https://www.elsevier.com/books/statistical-methods-in-the-atmospheric-sciences/wilks/978-0-12-385022-5

• The probability integral transform applies to all continuous distributions, not just Normal ones. The role of standardization in your code is unclear, in part because you haven't described what the code actually does or what the tables represent. For instance, the p-value depends on which parameter(s) are known and which are estimated. – whuber Jun 28 at 14:03
• Thanks. I edited the question and added further information about the algorithm and code. – maschu Jun 28 at 16:55


text:
# Find if there exists a path between two nodes in a directed graph

#### Algorithms Graph Algorithms

Get FREE domain for 1st year and build your brand new site

You are given a directed graph and two vertices on it. Your task is to find if there exists a path between the first vertex to the second vertex or not.

## Example

#### Input to construct the above graph:

Input:
No. of nodes in graph = 4
No. of edges in graph = 5
Edges:
1 2
2 3
2 4
3 1
3 4
No. of queries = 2
1 4
4 2
Output:
Yes
No

#### Explanation:

For the first query, the answer is Yes because we can construct a path as shown in the diagram below ( 1->2->4 ) but for the second query the answer is No because there are no outgoing edges from vertex four.

## Approach

To solve this problem, we can use either BFS (Breadth First Search) or DFS (Depth First Search) to find if there exists a path between two vertices.

Some important points:
1. For representing nodes we will use 1-indexing or in other words the nodes will be numbered from 1 to number_of_nodes.

2. To represent the graph we will use a 2-D vector in C++ and we will use the adjacency list representation as it gives us lower time and space complexity. We will resize the 2-D vector to contain vectors equal to no. of nodes.

std::vector <std::vector<int>> graph;
graph.resize(number_of_nodes);

## 1. Using BFS

Here we will use Breadth First Search in the solution. Take the first vertex as the source in BFS and if the second vertex is found in traversal print Yes otherwise No.

#### Pseudocode

isPathBFS(Graph G, node source, node end):
Queue Q
Q.enqueue( source ) //add the source node to the queue first

tag source as visited

while (Q is not empty):
v  =  Q.dequeue( )

for all neighbours w of v in Graph G
if w is end :
return true

if w is not visited :
Q.enqueue( w )
tag w as visited
return false

#### Example

In the Graph G in the image below, we find whether there exists a path between node 1 and node 6 using BFS. To find if there exists such a path, we will use BFS with node 1 as our source and check if node 6 exists in our traversal.

## Solution using BFS

• C++

### C++

// C++ program to check if there exists a path between two vertices of a graph.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//function definition
bool isPathBFS(vector <vector<int>>& graph, int nodes, int source, int end){
//BFS implementation

bool visited[nodes];
for(int i = 0;i<nodes;++i){
visited[i] = false;
}

queue <int> traversal;
traversal.push(source);
visited[source-1] = true;

while(!traversal.empty()){
//dequeue the front element
source = traversal.front();
traversal.pop();

for(int i = 0;i < (int)graph[source-1].size();++i){
if(graph[source-1][i]==end)
return true;

if(visited[graph[source-1][i]-1]==false){

traversal.push(graph[source-1][i]);
visited[graph[source-1][i]-1] = true;
}
}
}

return false;
}

int main(){
//input
int nodes;
cout << "No. of nodes in graph = ";
cin >> nodes;

int edges;
cout << "No. of edges in graph = ";
cin >> edges;

vector <vector<int>> graph;
graph.resize(nodes);

cout << "Edges:\n";
int source,end;

while(edges--){
cin >> source>>end;

//As we are using 1-indexing for nodes
if(source > nodes || end > nodes){
cout << "Invalid nodes.";
return 1;
}

graph[source-1].push_back(end);
}

int query;
cout << "No. of queries = ";
cin >> query;

while(query--){
cin >> source>>end;

//output
if(source > nodes || end > nodes){
cout << "Invalid nodes.\n";
continue;
}

if(isPathBFS(graph,nodes,source,end)){
cout << "Yes"<<"\n";
}else cout << "No"<<"\n";
}
return 0;
}

### Time Complexity ( for adjancency list representation )

• Worst case time complexity: O(V+E)
• Best case time complexity: Ω(1)
• Space complexity: O(V+E)
where V is the number of vertices and E is the number of edges.

## 2. Using DFS

Here we will use Depth First Search in the solution. Take the first vertex as the source in DFS and if the second vertex is found in traversal print Yes otherwise No.

#### Pseudocode

isPathDFS(Graph G, node source, node end):
Stack S
S.push( source )

tag source as visited

while(S is not empty):
v = S.top()
S.pop()

for all neighbours of w of v in Graph G:
if w is end :
return true

if w is not visited :
S.push( w )
tag w as visited

return false

#### Example

In the Graph G in the image below, we find whether there exists a path between node 1 and node 6 using DFS. To find if there exists such a path, we will use DFS with node 1 as our source and check if node 6 exists in our traversal.

## Solution using DFS

• C++

### C++

// C++ program to check if there exists a path between two vertices of a graph.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

//function definition
bool isPathDFS(vector <vector<int>>& graph, int nodes, int source, int end){
//DFS implementation

bool visited[nodes];
for(int i = 0;i<nodes;++i){
visited[i] = false;
}

stack <int> traversal;
traversal.push(source);
visited[source-1] = true;

while(!traversal.empty()){
//Pop the front element
source = traversal.top();
traversal.pop();

for(int i = 0;i < (int)graph[source-1].size();++i){
if(graph[source-1][i]==end)
return true;

if(visited[graph[source-1][i]-1]==false){

traversal.push(graph[source-1][i]);
visited[graph[source-1][i]-1] = true;
}
}
}

return false;
}

int main(){
//input
int nodes;
cout << "No. of nodes in graph = ";
cin >> nodes;

int edges;
cout << "No. of edges in graph = ";
cin >> edges;

vector <vector<int>> graph;
graph.resize(nodes);

cout << "Edges:\n";
int source,end;

while(edges--){
cin >> source>>end;

//As we are using 1-indexing for nodes
if(source > nodes || end > nodes){
cout << "Invalid nodes.";
return 1;
}

graph[source-1].push_back(end);
}

int query;
cout << "No. of queries = ";
cin >> query;

while(query--){
cin >> source>>end;

//output
if(source > nodes || end > nodes){
cout << "Invalid nodes.\n";
continue;
}

if(isPathDFS(graph,nodes,source,end)){
cout << "Yes"<<"\n";
}else cout << "No"<<"\n";
}
return 0;
}

### Time Complexity ( for adjancency list representation )

• Worst case time complexity: O(V+E)
• Best case time complexity: Ω(1)
• Space complexity: O(V+E)
where V is the number of vertices and E is the number of edges.

#### Tradeoffs between BFS and DFS approach

BFS can be useful to find the minimum number of edges between two nodes while DFS may not always give us the path with minimum number of edges as it may traverse one adjacent node very deeply before going to other neighbouring nodes (as BFS works level by level while DFS works depth wise).
For other differences between BFS vs DFS refer to the article : BFS vs DFS

Exercise: Modify the above algorithm to find any path between two vertices if it exists.

Also feel free to share your approach in the discussion thread below. Happy Coding :)

format: plain


text:
# Proper way to combine conditional probability distributions of the same random variable conditioned on a discrete variable ? (based on assumptions)

My question is the following. Let's say I have two probability distributions:

$f(x|b), g(x|c)$

$b$ and $c$ are discrete events while $x$ is a continuous variable, i.e., when the button b is pressed there is some distribution for the amount of rain fall the next day, $x$.

When the button $c$ is pressed there is a different distribution of rain fall the next day, $x$. Are there any strategies for estimating the distribution of rain fall if both buttons are pressed, i.e.,

$h(x|b,c)$ ?

And, what assumptions do those strategies rest on?

-
You call both of your random variables (i.e., your events) x, but it might make more sense to call one y. Then we can ask, are x and y independent? If not, do you know how x and y are related? Without knowing the answers, it is not possible to get the joint probability distribution. That is, it is impossible to answer your question. –  Joel W. May 30 '12 at 20:46
Can you say a and b are independant?i.e. p(a)*p(b)=p(a and b) –  Seth May 30 '12 at 21:40
Seth - yes I can assume independence of b & c (I think you mean b and c as referred to in the question). –  BrainPermafrost May 30 '12 at 21:50
Joel W. - well, the reason I only use x is that they are the same random variable. –  BrainPermafrost May 30 '12 at 21:52
I don't see how this question makes sense. All you know is that b and c give different distributions for x. You don't even know what those distributions are. It could be that if b occurs you always get f(x|b) even when c occurs. Or what if c dominates then even if b occurs you get g(x|c). Those would be dependent cases. What would independence of b and c tell you? –  Michael Chernick May 31 '12 at 1:02
show 1 more comment


text:
discretize.utils.cyl2cart¶

discretize.utils.cyl2cart(grid, vec=None)[source]

Take a grid defined in cylindrical coordinates $$(r, heta, z)$$ and transform it to cartesian coordinates.


text:
# Batch processing of image files

I recently had 178 JPEG files that weren’t behaving: Firefox and IE couldn’t display them. GIMP could read them and display them, and a GIMP Save As JPEG (after making no changes) created files that displayed properly in Firefox and IE, but I didn’t want to do that 178 times.

ImageMagick to the rescue. This free program, available for Windows, Mac, and Linux comes with several command line utilities, but the convert one is all I’ve ever needed. It has dozens and dozens of command-line options, but I didn’t even need any to fix these JPEGs. I just converted each to a BMP and then back, like this,

convert myfile.jpg myfile.bmp
convert myfile.bmp myfile.jpg

and then I had a JPEG file that displayed fine in the web browsers. To do this 178 times in Windows, I created a batch file that looked like this

convert %1.jpg %1.bmp
convert %1.bmp %1.jpg

and then used the output of dir /b *.jpg to create a batch file that called the two-line batch file for each image file.

If you need to process batches of images, it’s really worth looking through the command line options it offers, and of course the other ImageMagick utilities as well.

Since writing all that, I’ve found a possibly great new feature of ImageMagick: the ability to add XMP metadata to image files. (XMP is a profile of RDF from Adobe that has a lot of potential; I’ve complained here before about the lack of free command-line tools for adding and extracting XMP metadata from binary files.) Based on my tests and an online problem description, I don’t think this feature works properly yet. If anyone knows how to get ImageMagick or any other free command-line tool to add arbitrary metadata to image and PDF files (and of course, to extract it) please let me know.

By perusio on March 3, 2008 9:51 AM

Hmm, this seems to fit the bill (PDF+image files)

http://www.sno.phy.queensu.ca/~phil/exiftool/

It’s in Perl.

HTH

Thanks Perusio, This looks great! At first http://www.sno.phy.queensu.ca/~phil/exiftool/TagNames/XMP.html made me think that it could only handle predefined XMP fields, but http://www.sno.phy.queensu.ca/~phil/exiftool/config.html shows how to define your own metadata fields and store them as XMP. (I’m a big believer in the ability to store arbitrary metadata.) I will certainly be playing with this and reporting back on it.

Dude, that would really really be a case for getting Cygwin, if only so you can do a shell for-loop. (I, of course, download Cygwin first thing onto any Windows computer I have to deal with.)

Hi John,

When I set up a Windows machine, I add Firefox, Emacs, and Cygwin before I even change the desktop wallpaper, but I never looked too closely at Cygwin’s scripting. Looks like I should.\

for f in *.CR2
do
echo Processing $f exiftool -exif:OwnerName="Dave Pawson" -exif:Copyright="Dave Pawson 2008"$f
echo Backup  $f'_'original removed rm$f'_'original
done

exiftool would repay some investigation.

Hello,

in the Imagemagick package there is the command mogrify, using the same syntax as convert, but if you use wildcards in the filename, it will go through all files in the dir… so, for your case\

mogrify -format bmp *.jpg

and then\

mogrify -format jpg *.bmp

\

would have done the same as you showed…

Albin

By Tom Passin on March 3, 2008 11:32 PM

Oh, c’mon, you can do it with a Windows cmd file, too (this may wrap in the textarea) -

for %%v in (*.CR2) do echo Processing %%v & exiftool

-exif:OwnerName="Dave Pawson" -exif:Copyright="Dave Pawson 2008" %%v &

del %%v_original

\

Not that I’m agin *ix. I’ve been running a lot of them in virtual machines lately.\

Thanks Dave and Tom! (All note that Tom’s command should be written out as one line.)


text:
Next: Monte Carlo simulations Up: mlbmb Previous: The correlation integral

# Maximum likelihood methods

For the correlation dimension, maximum likelihood estimators have been derived by Takens (1985) and Ellner (1988). In their approach, the distribution function (3) is normalized, such that , with the consequence that the correlation entropy cannot be determined.

Now suppose we have a sample that consists of independent distances, with in the interval , in and in . The likelihood function for this doubly censored set of data is [Kendall and Stuart, 1979]

 (7)

where A is a permutation coefficient and is used for convenience. We now consider the case where the sample consists of distances calculated at embedding dimension , and distances calculated at embedding dimension . We also assume that the and distances are independent. The likelihood function for this case, , is the product of the likelihood functions and .

By solving the likelihood equations [Kendall and Stuart, 1979], we find the maximum likelihood estimators of the parameters , and . These are

 (8)

and
 (9)

with a similar expression for . The maximum likelihood estimator of the correlation entropy is
 (10)

where we used equation (3) and the property that a function of maximum likelihood estimators is itself a maximum likelihood estimator.

The asymptotic variances of the dimension and entropy estimators are obtained by inverting the information matrix [Kendall and Stuart, 1979]. We find

 (11)

and
 (12)

If , then and are uncorrelated. Moreover, the estimator of the entropy is equivalent to equation (6) if one substitutes and if the correlation integrals are based on independent distances.

The maximum likelihood estimator of the correlation dimension calculated at a single embedding dimension reads

 (13)

Its asymptotic variance is given by
 (14)

These equations are slight generalizations of Ellner's results. Note that the expressions for the double'' correlation dimension (equation (8)) and entropy (equation (10)) are only meaningful if the single'' correlation dimensions and (equation (13)) do not significantly differ.

Next: Monte Carlo simulations Up: mlbmb Previous: The correlation integral
webmaster@rullf2.xs4all.nl


text:
RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Trudy Inst. Mat. i Mekh. UrO RAN: Year: Volume: Issue: Page: Find

 Trudy Inst. Mat. i Mekh. UrO RAN, 2009, Volume 15, Number 4, Pages 183–194 (Mi timm435)

Minimax and viscosity solutions in optimization problems for hereditary systems

N. Yu. Lukoyanov

Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences

Abstract: For a dynamical system with discrete and distributed time delays, a control problem under disturbance or counteraction is considered. The problem is formalized in the context of the game-theoretical approach in the class of control strategies with memory. The problem is associated with a functional Hamilton–Jacobi type equation with coinvariant derivatives. The minimax and viscosity approaches to a generalized solution of this equation are discussed. It is shown that, under the same condition at the right endpoint, the minimax and viscosity solutions coincide, thereby uniquely defining the functional of optimal guaranteed result in the control problem

Keywords: optimal control, differential games, time-delay systems, Hamilton–Jacobi equations, minimax solution, viscosity solution.

Full text: PDF file (213 kB)
References: PDF file   HTML file

English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2010, 269, suppl. 1, S214–S225

Document Type: Article
UDC: 517.977

Citation: N. Yu. Lukoyanov, “Minimax and viscosity solutions in optimization problems for hereditary systems”, Trudy Inst. Mat. i Mekh. UrO RAN, 15, no. 4, 2009, 183–194; Proc. Steklov Inst. Math. (Suppl.), 269, suppl. 1 (2010), S214–S225

Citation in format AMSBIB
\Bibitem{Luk09} \by N.~Yu.~Lukoyanov \paper Minimax and viscosity solutions in optimization problems for hereditary systems \serial Trudy Inst. Mat. i Mekh. UrO RAN \yr 2009 \vol 15 \issue 4 \pages 183--194 \mathnet{http://mi.mathnet.ru/timm435} \elib{http://elibrary.ru/item.asp?id=12952764} \transl \jour Proc. Steklov Inst. Math. (Suppl.) \yr 2010 \vol 269 \issue , suppl. 1 \pages S214--S225 \crossref{https://doi.org/10.1134/S0081543810060179} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84962468865}

• http://mi.mathnet.ru/eng/timm435
• http://mi.mathnet.ru/eng/timm/v15/i4/p183

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. N. Yu. Lukoyanov, “On Hamilton–Jacobi formalism in time-delay control systems”, Tr. IMM UrO RAN, 16, no. 5, 2010, 269–277
2. Bayraktar E., Keller Ch., “Path-Dependent Hamilton–Jacobi Equations in Infinite Dimensions”, J. Funct. Anal., 275:8 (2018), 2096–2161
•  Number of views: This page: 279 Full text: 100 References: 31


text:
# Does light from steady sources bear any observable imprint of the dispersive intergalactic medium? [IMA]

There has recently been some interest in the prospect of detecting ionized intergalactic baryons by examining the properties of incoherent light from background cosmological sources, namely quasars. Although the paper by \cite{lieu13} proposed a way forward, it was refuted by the later theoretical work of \cite{hir14} and observational study of \cite{hal16}. In this paper we investigated in detail the manner in which incoherent radiation passes through a dispersive medium both from the frameworks of classical and quantum electrodynamics, which led us to conclude that the premise of \cite{lieu13} would only work if the pulses involved are genuinely classical ones involving many photons per pulse, but unfortunately each photon must not be treated as a pulse that is susceptible to dispersive broadening. We are nevertheless able to change the tone of the paper at this juncture, by pointing out that because current technology allows one to measure the phase of individual modes of radio waves from a distant source, the most reliable way of obtaining irrefutable evidence of dispersion, namely via the detection of its unique signature of a quadratic spectral phase, may well be already accessible. We demonstrate how this technique is only applied to measure the column density of the ionized intergalactic medium.

R. Lieu and L. Duan
Fri, 1 Dec 17
47/68

Comments: 21 pages, 67 equations, ApJ in press

|

# Quantum chaos of dark matter in the Solar System [CL]

We perform time-dependent analysis of quantum dynamics of dark matter particles in the Solar System. It is shown that this problem has similarities with a microwave ionization of Rydberg atoms studied previously experimentally and analytically. On this basis it is shown that the quantum effects for chaotic dark matter dynamics become significant for dark matter mass ratio to electron mass being smaller than $2 \times 10^{-15}$. Below this border multiphoton diffusion over Rydberg states of dark matter atom becomes exponentially localized in analogy with the Anderson localization in disordered solids. The life time of dark matter in the Solar System is determined in dependence on mass ratio in the localized phase and a few photon ionization regime. Various implications of these quantum results are discussed for the capture of dark matter from Galaxy and its steady-state density distribution.

D. Shepelyansky
Thu, 23 Nov 17
48/52

# Quantum chaos of dark matter in the Solar System [CL]

We perform time-dependent analysis of quantum dynamics of dark matter particles in the Solar System. It is shown that this problem has similarities with a microwave ionization of Rydberg atoms studied previously experimentally and analytically. On this basis it is shown that the quantum effects for chaotic dark matter dynamics become significant for dark matter mass ratio to electron mass being smaller than $2 \times 10^{-15}$. Below this border multiphoton diffusion over Rydberg states of dark matter atom becomes exponentially localized in analogy with the Anderson localization in disordered solids. The life time of dark matter in the Solar System is determined in dependence on mass ratio in the localized phase and a few photon ionization regime. Various implications of these quantum results are discussed for the capture of dark matter from Galaxy and its steady-state density distribution.

D. Shepelyansky
Thu, 23 Nov 17
25/52

# Quantum to classical transition in the Hořava-Lifshitz quantum cosmology [CL]

A quasi-Gaussian quantum superposition of Ho\v{r}ava-Lifshitz (HL) stationary states is built in order to describe the transition of the quantum cosmological problem to the related classical dynamics. The obtained HL phase-space superposed Wigner function and its associated Wigner currents describe the conditions for the matching between classical and quantum phase-space trajectories. The matching quantum superposition parameter is associated to the total energy of the classical trajectory which, at the same time, drives the engendered Wigner function to the classical stationary regime. Through the analysis of the Wigner flows, the quantum fluctuations that distort the classical regime can be quantified as a measure of (non)classicality. Finally, the modifications to the Wigner currents due to the inclusion of perturbative potentials are computed in the HL quantum cosmological context. In particular, the inclusion of a cosmological constant provides complementary information that allows for connecting the age of the Universe with the overall stiff matter density profile.

A. Bernardini, P. Leal and O. Bertolami
Wed, 8 Nov 17
57/84

# Recent progress on the description of relativistic spin: vector model of spinning particle and rotating body with gravimagnetic moment in General Relativity [CL]

We review the recent results on development of vector models of spin and apply them to study the influence of spin-field interaction on the trajectory and precession of a spinning particle in external gravitational and electromagnetic fields. The formalism is developed starting from the Lagrangian variational problem, which implies both equations of motion and constraints which should be presented in a model of spinning particle. We present a detailed analysis of the resulting theory and show that it has reasonable properties on both classical and quantum level. We describe a number of applications and show how the vector model clarifies some issues presented in theoretical description of a relativistic spin: A) One-particle relativistic quantum mechanics with positive energies and its relation with the Dirac equation and with relativistic {\it Zitterbewegung}; B) Spin-induced non commutativity and the problem of covariant formalism; C) Three-dimensional acceleration consistent with coordinate-independence of the speed of light in general relativity and rainbow geometry seen by spinning particle; D) Paradoxical behavior of the Mathisson-Papapetrou-Tulczyjew-Dixon equations of a rotating body in ultra relativistic limit, and equations with improved behavior.

A. Deriglazov and W. Ramirez
Mon, 23 Oct 17
52/52

Comments: Invited review article for the Journal “Advances in Mathematical Physics”. Based on the recent works: arXiv:1312.6247, arXiv:1406.6715, arXiv:1409.4756, arXiv:1509.05357, arXiv:1511.00645, arXiv:1609.00043. 61 pages, 3 figures

# Matter-wave coherence limit owing to cosmic gravitational wave background [CL]

We study matter-wave interferometry in the presence of a stochastic background of gravitational waves. It is shown that if the background has a scale-invariant spectrum over a wide bandwidth (which is expected in a class of inflationary models of Big Bang cosmology), then separated-path interference cannot be observed for a lump of matter of size above a limit which is very insensitive to the strength and bandwidth of the fluctuations, unless the interferometer is servo-controlled or otherwise protected. For ordinary solid matter this limit is of order 1–10 mm. A servo-controlled or cross-correlated device would also exhibit limits to the observation of macroscopic interference, which we estimate for ordinary matter moving at speeds small compared to c.

A. Steane
Tue, 17 Oct 17
44/163


text:
# Abstract Nonsense

## Unit Group of a Finite Field is Cyclic

Point of Post: In this post we prove the basic fact that if $k$ is a finite field then $U(k)$ is cyclic.

$\text{ }$

Motivation

A very useful fact in both field and group theory is that if $k$ is a finite field then the group of units $U(k)$ is cyclic of order $|k|-1$. There are several ways one may go about doing this. In particular, there are two striking group theoretic facts about $U(k)$ which one hope characterize it. Namely, from basic field theory we know for any polynomial $p(x)\in k[x]$ one has that the number of roots of $p(x)$ in $k$ is bounded above by $\deg(p(x))$. In particular, using only the operation of the group we have that $x^n=1$ has at most solutions in $k$. The other interesting fact, which is easily implied by the bounded amount of roots $x^n=1$, is that $U(k)$ has at most one cyclic subgroup of a given order (this is clearly implied by the previous property since if $|g|=n$ and $C_n$ is the cyclic subgroup generated by $g$ then by Lagrange’s Theorem $x^n=x^{|C_n|}=1$ for each $x\in C_n$ and so, in particular $C_n$ constitutes $n$ solutions of $x^n=1$ and so clearly there can’t be another distinct cyclic subgroup of order $n$). So, we prove that both of these properties characterize cyclic groups and so, in particular, $U(k)$ is cyclic.

$\text{ }$

The Characterizations

$\text{ }$

Our first proof makes clever use of Sylow’s theorems:

$\text{ }$

Theorem: Let $G$ be a finite group, say with $|G|=p_1^{\alpha_1}\cdots p_m^{\alpha_m}$, and the property that $x^n=1$ has at most $n$ solutions in $G$ for every $n\in\mathbb{N}$. Then, $G$ is cyclic.

Proof: Let $k\in[m]$  and let $P\in\text{Syl}_{p_k}(G)$. We claim that $P\unlhd G$. Indeed, since $g^{|P|}=1$ for every $g\in P$ we have that for every $g\notin P$ one has that $g^{|P|}\ne 1$. Thus, clearly there does not exist another $Q\in\text{Syl}_p(G)$ otherwise choosing $g\in Q-P$ would produce another element of $G$ for which $g^{|P|}=g^{|Q|}=1$ which contradicts that there at most $|P|$ solutions to the equation $x^{|P|}=1$. But, since all Sylow $p$-subgroups are conjugate and we have found that there is only one we may conclude that $P\unlhd G$. What we now claim is that $P$ is cyclic. Indeed, by Sylow’s theorems we may find some $H\leqslant P$ with $|H|=p_k^{\alpha_k-1}$. Since then $H$ contains $p_k^{\alpha_k-1}$ solutions to $x^{p_k^{\alpha_k-1}}=1$ we have that it contains all such solutions. In particular, choosing $g\in P-H$ we find that $g^{p_k^{\alpha_k-1}}\ne 1$ and since $g^{p_k^{\alpha_k}}=1$ we may conclude from basic theory that $|g|=p_k^{\alpha_k}$ and so $P$ is cyclic as claimed. Now since all the Sylow $p$-subgroups of $G$ are normal we know from basic Sylow theory that $G\cong P_1\times\cdots\times P_m$ where $P_k$ is the unique element of $\text{Syl}_{p_k}(G)$. But since each $P_k$ is cyclic and $(|P_i|,|P_j|)=1$ for $i\ne j$ we have from basic group theory that $G$ is cyclic. $\blacksquare$

$\text{ }$

Our next theorem shows that the other condition satisfied by $U(k)$ about having at most one cyclic group of each order implies cyclicity. In particular:

$\text{ }$

Theorem: Let $G$ be a finite group and suppose that for each divisor $d$ of $|G|$ one has that $G$ has at most one cyclic subgroup of order $d$ then $G$ is cyclic.

Proof: Let $c_d(G)$ denote the number of cyclic subgroups of $G$ of size $d$. We claim now that

$\text{ }$

$\displaystyle \sum_{d\mid |G|}c_d(G)\varphi(d)=|G|\quad\mathbf{(1)}$

$\text{ }$

where $\varphi$ is the Euler totient function. Indeed, evidently

$\text{ }$

$\displaystyle \sum_{d\mid |G|}\;\;\sum_{x\text{ s.t. }|x|=d}1=|G|\quad\mathbf{(2)}$

$\text{ }$

Now, how do we count how many elements have order $d$ in $G$? Well, note that if $|x|=d$ then $\langle x\rangle$ is a cyclic subgroup of $G$ of order $d$, and moreover this is the only cyclic subgroup of $G$ of order $d$ that contains $x$. Indeed, for if $H$ were another such subgroup then since $x\in H$ we’d have that $G=\langle x\rangle\subseteq H$ and since $|H|=|G|=d$ we’d have that $G=H$. So, the number of elements $x\in G$ with $|x|=d$ is equal to

$\text{ }$

$\displaystyle \sum_{C_d\text{: cyclic subgroup of order }d}\#\{x\in C_d:|x|=d\}$

$\text{ }$

That said, note that $\#\{x\in C_d:|x|=d\}$ is equal to $\#\{x\in C_d:x\text{ generates }C_d\}$ which, by basic group theory, is equal to $\varphi(d)$ and so

$\text{ }$

\displaystyle \begin{aligned}\sum_{C_d\text{: cyclic subgroup of order }d}\#\{x\in C_d:|x|=d\} &=\sum_{C_d\text{: cyclic subgroup of order }d}\varphi(d)\\ & \\ &=c_d(G)\varphi(d)\end{aligned}

$\text{ }$

and so our claim laid out in $\mathbf{(1)}$ follows by inputting this information into $\mathbf{(2)}$. Now, it is a common fact that

$\text{ }$

$\displaystyle \sum_{d\mid |G|}\varphi(d)=|G|$

$\text{ }$

and since we assumed that $c_d(G)\leqslant 1$ for each $d\mid |G|$ it is easy to deduce from this and $\mathbf{(1)}$ that $c_d(G)=1$ for all $d\mid n$. In particular, $c_{|G|}(G)=1$, but this is equivalent to saying that $G$ is cyclic. The conclusion follows. $\blacksquare$

$\text{ }$

Remark: Although we used it later in the proof, the fact that the sum over $d\mid |G|$ of $\varphi(d)$ is equal to $|G|$ was not used in the derivation of $\mathbf{(1)}$. In particular, taking $G=\mathbb{Z}_n$ so that $c_d(G)=1$ for all $d\mid |G|=n$ actually implies the more common formula that the sum over $d\mid n$ of $\varphi(d)$ is $n$.

$\text{ }$

From both of these we get, as justified in the motivation, the following corollary:

$\text{ }$

Corollary: Let $k$ be a finite field, then $U(k)$ is cyclic.

$\text{ }$

$\text{ }$

References:

1.  Dummit, David Steven., and Richard M. Foote. Abstract Algebra. Hoboken, NJ: Wiley, 2004. Print.

September 21, 2011 -

1. […] The result has already been proven for and so it suffices to prove this for . To see this note that there is a natural morphism which […]

Pingback by The Unit and Automorphism Group of Z/nZ (Pt. I) « Abstract Nonsense | September 21, 2011 | Reply

2. […] that is cyclic is a little wishy-washy. A more rigorous, and more general proof can be found in this post of […]

Pingback by Groups of Order pq (Pt. II) « Abstract Nonsense | February 28, 2012 | Reply

3. […] just the elementary abelian group . Multiplicatively we know that looks like since, as we have proven before, finite subgroups of the multiplicative group of a field are cyclic. Now, note that this was […]

Pingback by Finite Fields « Abstract Nonsense | April 12, 2012 | Reply

4. […] Proof: If is finite then is finite and the conclusion follows from the cyclicity of . […]

Pingback by Separable Extensions (Pt. II) « Abstract Nonsense | May 4, 2012 | Reply


text:
## College Algebra 7th Edition

$a_{n}=(-1)^{n+1}\ 5^{n}$
We are given: $5, -25, 125, -625$, ... We see that the terms in the sequence take on powers of $5$. In addition, we notice that the sign alternates. We find the pattern: $a_1=(-1)^{2}\ 5^{1}$ $a_2=(-1)^{3}\ 5^{2}$ $a_3=(-1)^{4}\ 5^{3}$ $a_4=(-1)^{5}\ 5^{4}$ ... $a_{n}=(-1)^{n+1}\ 5^{n}$


text:
Publication 2006 Issue No. 10 - October Abstract - An Effective and Efficient Exact Match Retrieval Scheme for Symbolic Image Database Systems Based on Spatial Reasoning: A Logarithmic Search Time Approach
An Effective and Efficient Exact Match Retrieval Scheme for Symbolic Image Database Systems Based on Spatial Reasoning: A Logarithmic Search Time Approach
October 2006 (vol. 18 no. 10)
pp. 1368-1381
 ASCII Text x P. Punitha, D.S. Guru, "An Effective and Efficient Exact Match Retrieval Scheme for Symbolic Image Database Systems Based on Spatial Reasoning: A Logarithmic Search Time Approach," IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 10, pp. 1368-1381, October, 2006.
 BibTex x @article{ 10.1109/TKDE.2006.154,author = {P. Punitha and D.S. Guru},title = {An Effective and Efficient Exact Match Retrieval Scheme for Symbolic Image Database Systems Based on Spatial Reasoning: A Logarithmic Search Time Approach},journal ={IEEE Transactions on Knowledge and Data Engineering},volume = {18},number = {10},issn = {1041-4347},year = {2006},pages = {1368-1381},doi = {http://doi.ieeecomputersociety.org/10.1109/TKDE.2006.154},publisher = {IEEE Computer Society},address = {Los Alamitos, CA, USA},}
 RefWorks Procite/RefMan/Endnote x TY - JOURJO - IEEE Transactions on Knowledge and Data EngineeringTI - An Effective and Efficient Exact Match Retrieval Scheme for Symbolic Image Database Systems Based on Spatial Reasoning: A Logarithmic Search Time ApproachIS - 10SN - 1041-4347SP1368EP1381EPD - 1368-1381A1 - P. Punitha, A1 - D.S. Guru, PY - 2006KW - Exact match retrievalKW - direction of referenceKW - modified binary searchKW - spatial relationshipKW - symbolic imageKW - symbolic image database.VL - 18JA - IEEE Transactions on Knowledge and Data EngineeringER -
In this paper, a novel method of representing symbolic images in a symbolic image database (SID) invariant to image transformations that is useful for exact match retrieval is presented. The relative spatial relationships existing among the components present in an image are perceived with respect to the direction of reference [15] and preserved by a set of triples. A distinct and unique key is computed for each distinct triple. The mean and standard deviation of the set of keys computed for a symbolic image are stored along with the total number of keys as the representatives of the corresponding image. The proposed exact match retrieval scheme is based on a modified binary search technique and, thus, requires O(log n) search time in the worst case, where n is the total number of symbolic images in the SID. An extensive experimentation on a large database of 22,630 symbolic images is conducted to corroborate the superiority of the model. The effectiveness of the proposed representation scheme is tested with standard testbed images.

[1] V.N. Gudivada, “$\Theta {\rm{R}}{\hbox{-}}\rm string$ : A Geometry-Based Representation for Efficient and Effective Retrieval of Images by Spatial Similarity,” IEEE Trans. Knowledge and Data Eng., vol. 10, no. 3, pp. 504-512, May/June 1998.
[2] D. Maltoni, D. Maio, A.J. Jain, and S. Prabhakar, Handbook of Fingerprint Recognition. Springer Professional Computing, 2005.
[3] S.C. Orphanoudakis, C. Chronaki, and S. Kostomanolakis, “I2C: A System for the Indexing, Storage and Retrieval of Medical Images by Content,” J. Medical Informatics, vol. 19, no. 2, pp. 109-122, 1994.
[4] E.G.M. Petrakis and C. Faloustsos, “Similarity Searching in Medical Image Databases,” IEEE Trans. Knowledge and Data Eng., vol. 9, no. 3, pp. 435-447, 1997.
[5] S.K. Chang, Q.Y. Shi, and C.W. Yan, “Iconic Indexing by 2D Strings,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 9, no. 5, pp. 413-428, Sept. 1987.
[6] S.K. Chang, E. Jungert, and Y. Li, “Representation and Retrieval of Symbolic Pictures Using Generalized 2D Strings,” SPIE Proc. Conf. Visual Comm. and Image Processing, pp. 1360-1372, 1989.
[7] C.C. Chang and T.C. Wu, “Retrieving the Most Similar Symbolic Pictures from Pictorial Databases,” Information Processing and Management, vol. 28, no. 5, pp. 581-588, 1992.
[8] T.C. Wu and C.C. Chang, “Application of Geometric Hashing to Iconic Database Retrieval,” Pattern Recognition Letters, vol. 15, pp. 871-876, 1994.
[9] P.W. Huang and Y.R. Jean, “Using 2D C+ Strings as Spatial Knowledge Representation for Image Database Systems,” Pattern Recognition, vol. 27, no. 9, pp. 1249-1257, 1994.
[10] X.M. Zhou and C.H. Ang, “Retrieving Similar Pictures from Pictorial Database by an Improved Hashing Table,” Pattern Recognition Letters, vol. 18, pp. 751-758, 1997.
[11] X.M. Zhou, C.H. Ang, and T.W. Ling, “Image Retrieval Based on Object's Orientation Spatial Relationship,” Pattern Recognition Letters, vol. 22, pp. 469-477, 2001.
[12] E.G.M. Petrakis and S.C. Orphanoudakis, “A Methodology for the Representation, Indexing and Retrieval of Images by Content,” Image and Vision Computing, vol. 8, no. 11, pp. 504-521, 1993.
[13] E.G.M. Petrakis, “Design and Evaluation of Spatial Similarity Approaches for Image Retrieval,” Image and Vision Computing, vol. 20, pp. 59-76, 2002.
[14] A.K. Majumdar, I. Bhattacharya, and A.K. Saha, “An Object-Oriented Fuzzy Data Model for Similarity Detection in Image Databases,” IEEE Trans. Knowledge and Data Eng., vol. 14, no. 5, pp. 1186-1189, Sept./Oct. 2002.
[15] D.S. Guru and P. Punitha, “An Invariant Scheme for Exact Match Retrieval of Symbolic Images Based Upon Principal Component Analysis,” J. Pattern Recognition Letters, vol. 25, no. 1, pp. 73-86, 2004.
[16] S.K. Chang and Y. Li, “Representation of Multi-Resolution Symbolic and Binary Pictures Using 2D H Strings,” Proc. IEEE Workshop Languages for Automata, pp. 190-195, 1988.
[17] S.Y. Lee and F.J. Hsu, “2D C String: A New Spatial Knowledge Representation for Image Database System,” Pattern Recognition, vol. 23, no. 10, pp. 1077-1087, 1990.
[18] S.Y. Lee and F.J. Hsu, “Picture Algebra for Spatial Reasoning of Iconic Images Represented in 2D C String,” Pattern Recognition Letters, vol. 12, no. 7, pp. 425-435, 1991.
[19] C.C. Chang and D.C. Lin, “A Spatial Data Representation: An Adaptive 2D H String,” Pattern Recognition Letters, vol. 17, pp. 175-185, 1996.
[20] Y.I. Chang and H.Y. Ann, “A Note On Adaptive 2D-H Strings,” Pattern Recognition Letters, vol. 20, pp. 15-20, 1999.
[21] S.Y. Lee, M.K. Shan, and W.P. Yang, “Similarity Retrieval of Iconic Image Databases,” Pattern Recognition, vol. 22, no. 6, pp. 675-682, 1989.
[22] S.Y. Lee and M.K. Shan, “Access Methods of Image Databases,” Pattern Recognition and Artificial Intelligence, vol. 4, no. 1, pp. 27-44, 1990.
[23] S.Y. Lee and F.J. Hsu, “Spatial Reasoning and Similarity Retrieval of Images Using 2D C String Knowledge Representation,” Pattern Recognition, vol. 25, no. 3, pp. 305-318, 1992.
[24] S.K. Bhatia and C.L. Sabharwal, “A Fast Implementation of a Perfect Hash Function for Picture Objects,” Pattern Recognition, vol. 27, no. 3, pp. 365-375, 1994.
[25] C.L. Sabharwal and S.K. Bhatia, “Perfect Hash Table Algorithm for Image Databases Using Negative Associated Values,” Pattern Recognition, vol. 28, no. 7, pp. 1091-1101, 1995.
[26] C.L. Sabharwal and S.K. Bhatia, “Image Databases and Near Perfect Hash Table,” Pattern Recognition, vol. 30, no. 11, pp. 1867-1876, 1997.
[27] C.C. Chang, “Spatial Match Retrieval of Symbolic Pictures,” Information Science and Eng., vol. 7, pp. 405-422, 1991.
[28] C.C. Chang and T.C. Wu, “An Exact Match Retrieval Scheme Based upon Principal Component Analysis,” Pattern Recognition Letters, vol. 16, pp. 465-470, 1995.
[29] K. Segupta and K.L. Boyer, “Organising Large Structural Modelbases,” IEEE Trans. Pattern Recognition and Machine Intelligence, vol. 17, no. 4, pp. 321-332, Apr. 1995.
[30] B.T. Messmer and H. Bunke, “Fast Error Correcting Graph Isomorphism Based on Model Precompilation,” technical report, Univ. of Bern, Switerland, 1996.
[31] P. Korn, N. Sidiropulos, C. Faloustsos, E. Siegel, and Z. Proptopapas, “Fast and Effective Retrieval of Medical Tumor Shapes,” IEEE Trans. Knowledge and Data Eng., vol. 10, no. 6, pp. 889-904, Nov./Dec. 1998.
[32] Q. Jiang and W. Zhang, “An Improved Method for Finding Nearest Neighbors,” Pattern Recognition Letters, vol. 14, no. 7, pp. 531-535, 1993.
[33] A.K. Ghosh, P. Chaudhuri, and C.A. Murthy, “On Visualization and Aggregation of Nearest Neighbor Classifiers,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 27, no. 10, pp. 1592-1602, Oct. 2005.
[34] G. Petraglia, M. Sebillo, M. Tucci, and G. Tortora, “A Normalized Index for Image Databases,” Intelligent Image Database Systems, 1996.
[35] D.S. Guru, P. Punitha, and P. Nagabhushan, “Archival and Retrieval of Symbolic Images: An Invariant Scheme Based on Triangular Spatial Relationship,” Pattern Recognition Letters, vol. 24, no. 14, pp. 2397-2408, 2003.
[36] G. Petraglia, M. Sebillo, M. Tucci, and G. Tortora, “Virtual Images for Similarity Retrieval in Image Databases,” IEEE Trans. Knowledge and Data Eng., vol. 13, no. 6, pp. 951-967, Nov./Dec. 2001.
[37] D.E. Sciascio, M. Mongiello, F.M. Donini, and L. Allegretti, “Retrieval by Spatial Similarity: An Algorithm and Comparative Evaluation,” Pattern Recognition Letters, vol. 25, no. 14, pp. 1633-1645, 2004.
[38] D.S. Guru, H.J. Raghavendra, and M.G. Suraj, “An Adaptive Binary Search Based Sorting by Insertion: An Efficient and Simple Algorithm,” Statistics and Applications, vol. 2, pp. 85-96, 2000.
[39] D.S. Guru, “Towards Accurate Recognition of Objects Employing a Partial Knowledge Base: Some New Approaches,” PhD thesis, Dept. of Studies in Computer Science, Univ. of Mysore, Manasagangothri, Mysore, India, 2000.
[40] V.N. Gudivada and V.V. Raghavan, “Design and Evaluation of Algorithms for Image Retrieval by Spatial Similarity,” ACM Trans. Information Systems, vol. 13, no. 2, pp. 115-144, 1995.
[41] P. Bollmann, F. Jochum, U. Reiner, V. Weissmann, and H. Zuse, “The LIVE-Project-Retrieval Experiments Based on Evaluation Viewpoints,” Proc. Eighth Ann. Int'l ACM SIGIR Conf. Research and Development in Information Retrieval (SIGIR '85), pp. 213-214, 1985.
[42] R. Dinesh and D.S. Guru, “Mathematical Morphology Based Corner Detection Scheme: A Non-Parametric Approach,” Proc. Fourth Indian Conf. Computer Vision, Graphics and Image Processing (ICVGIP '04), pp. 76-81, Dec. 2004.
[43] R. Dinesh and D.S. Guru, “Corner Detection and Interpretation of Boundary Segments Useful for Production of Symbolic Images for 2D Objects,” Proc. Int'l Conf. Recent Trends in Information Systems (IRIS '06), 2006.

Index Terms:
Exact match retrieval, direction of reference, modified binary search, spatial relationship, symbolic image, symbolic image database.
Citation:
P. Punitha, D.S. Guru, "An Effective and Efficient Exact Match Retrieval Scheme for Symbolic Image Database Systems Based on Spatial Reasoning: A Logarithmic Search Time Approach," IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 10, pp. 1368-1381, Oct. 2006, doi:10.1109/TKDE.2006.154


text:
# Questions tagged [network]

The tag has no usage guidance.

29 questions
Filter by
Sorted by
Tagged with
103 views

### Could a scientist use the internet to detect gravitational waves?

According to my understanding (I'm not a physicist just a fan), LIGO measures the changes in two path's lengths to detect gravitational waves by sending a particle down each path at the constant speed ...
18 views

### Is it possible to implement the Invaded Cluster Algorithm on a network of Ising spins rather than a lattice?

My main concern is how to know if a cluster has percolated the network. For a periodic square lattice it is easy to determine if the cluster percolates by looking at the size of the cluster (as given ...
93 views

### Calculate the scattering matrix of a 3-port lumped element network [closed]

I can get S11 and S12 by terminating port 2 and 3 with Z0 and Zr respectively. But when I try to calculate S13 it seems less straight forward. The following is the network, taken from Gao, J. The ...
76 views

### What are exactly “norms” in spin networks? Are there any non-quantum spin networks?

Roger Penrose proposed a series of networks from which, fundamentally, space-time would emerge, called spin networks (https://en.wikipedia.org/wiki/Spin_network) In this article, it is said: ...
69 views

### Why does S11 seem to be independent of transmission media in this RF transmission experiment?

Hi friends I am starting to characterize a system in which we will plan to measure the response of a sample of liquid to radio waves. In order to do this I am exciting two antennas with the ports of ...
35 views

### In loop quantum gravity what is considered the initial conditions?

In LQG, the Universe starts off not from a singularity but of finite size. And there may be the idea of a pre-big bang crunch. Assuming the Universe is symmetric in time about the 'big bang'. What ...
14 views

### What influences the variance of signal transmission speed?

I'm currently thinking about the various sources that influence time when it is synchronized with the NTP protocol. One of them is the physical layer (OSI-model). When sending a bit over a cable, ...
233 views

### How does particle physics use deep neural networks to find particles?

Does anyone use deep learning: RNN, CNN or any other architecture of deep neural networks to asses the standard model or to detect new or unseen particles? What's the status these days in this ...
69 views

### Entropy of natural networks [duplicate]

How does one define the entropy of a natural network (say for example, a river network, or a morphological skeletal network of a lake in the figure below) ? For example, the following report suggests ...
85 views

### Percolation theory: What is the critical amplitude for the “backbone” of a 2-D network?

Disclaimer: I am just learning about percolation theory for the first time, so I am not too familiar with some of the terminology. Suppose you have a 2-D square lattice with bonds connecting sites. ...
254 views

### How to compute entropy of networks? (Boltzmann microstates and Shannon entropy) [closed]

I also asked in SO here a few days ago, thought it may be also interesting for physics-related answers. I would like to model a network as a system. A particular topology (configuration of edges ...
34 views

### How do low voltage differential signals transmit bits

For example: There is Din+ connected to pin a1 and Din- to pin a2. Suppose I am sending "0101". How does it get sent? If there was only Din connected to Pin a1, which has a voltage supply to the bank ...
121 views

### What is the physical interpretation of inductors and capacitors equations in Frequency(s) domain?

s-domain modelling of capacitor and inductor equation: V(s)=LsI(s)−Li(0−) I(s)=CsV(s)−Cv(0−)
71 views

### Scalar fields of graphs

I am trying to find literature on the propagation of scalar fields over random graphs. Think of a network of ideal resistors (with a given degree distribution), with a voltage source at a random node....
75 views

399 views

### Resistance Distance in large electrical networks

I am not tremendously familiar with electrical circuits (I have some memories, but too long ago) and now I have come accross a problem where I need to compute the resistance distance in a graph. So, ...
67 views

### What are the first couple terms of the Taylor series for the evolution of this network of capacitors and resistors?

note: This is a computational problem, and I only need approximate accuracy, so the overall goal is, for a given accuracy and $\Delta t$ to compute the state of the system at $t+\Delta t$ to within ...
80 views

### How can the response at the terminal end of an infinite ladder network be solved?

In a recent post: How can the transfer function of an infinite ladder network be used to solve real world problems? I reference how one can solve the transfer function (impedance) of an infinite ...
756 views

### How can the transfer function of an infinite ladder network be used to solve real world problems?

In his lectures on Physics, Feynman illustrates a mathematical 'trick' in formulating the impedance of an infinite ladder, LC network. It basically counts on the assumption that adding one more 'rung' ...
450 views

### How does the spinglass algorithm work when used for community detection in networks?

I am reading the article "Statistical Mechanics of Community Detection" by Jörg Reichardt and Stefarn Bornholdt, which describes how to use the spinglass model from physics to determine communities in ...
71 views

### Any fractal physical model that generates time series which demonstrate heavy-tailed (non-Gaussian) behavior in some form?

I know that fractal structures have power-laws in various forms "hidden" in them. I am looking for the most simple fractal model that I can find that generates time series with, say, Pareto-...
1k views

### Dialing emergency numbers with no network available. How? [closed]

When the network is not available on my phone, it says "emergency calls only". It means that even if I'm in the middle of the desert, with no towers in the vicinity, I can dial the emergency number. ...
651 views

### Building a Faraday cage for mobile networks that is transparent for optical wavelenghts

A friend of mine is working on an architectonic project, where she designs a Faraday cage type of open space built in parks or other public places. The initial thought is to build it from some sort of ...
94 views

### Examples of evolving networks in physics [closed]

I'm a master student working on networks analysis in general. A network is something that has nodes and there are links between the nodes. Nodes and links could have attributes. An evolving network is ...
2k views

### What is the difference between scale-free network and small-world network? [closed]

What is the difference between scale-free network and small-world network? I can't understand from the definitions around the web if they are both the same name for one thing. Do both follow a power-...
308 views

### Why isn't data lost when sent over large distances?

I was thinking about how information is sent, for example through the atmosphere. There are plenty of obstacles, as well diffraction, etc. Still, no information is lost. How is information sent to ...
134 views

### Book reviewing current state of research on complex networks [closed]

Can anybody recommend a book reviewing the current state of knowledge and active research on complex networks? Not primarily a textbook but a true review of the field - ideally with references to ...


text:
Tutorial:Machine Learning For Prediction of Relapse in Cancer - Part 2 - Building A Random Forest Classifier
0
83
Entering edit mode
9.4 years ago
Nicholas Spies ★ 1.2k

This tutorial is part of a series illustrating basic concepts and techniques for machine learning in R. We will try to build a classifier of relapse in breast cancer. The analysis plan will follow the general pattern (simplified) of a recent paper.

This follows from: Machine learning for cancer classification - part 1 - preparing the data sets. This part covers how to build a Random Forest classification model to predict relapse in breast cancer from microarray expression data. We make the assumption that the data sets will be in the correct format as produced in part 1. The data sets in this tutorial are the 'training data' from the prior tutorial, retrieved from GSE2034. In a subsequent tutorial we will apply the classifier built here to the 'test data' (GSE2990) also downloaded in part 1. To avoid the hassle of Copy-Pasting every block of code, the full script can be downloaded here. But, first, let's review the basic principles of the Random Forests method.

### Figure 1. A Random Forest is built one tree at a time.

A Random Forest is a collection of decision trees. Each tree gets a "vote" in classifying. There are two components of randomness involved in the building of a Random Forest. First, at the creation of each tree, a random subsample of the total data set is selected to grow the tree. Second, at each node of the tree, a well-performing gene from a random subset of all genes is chosen as a "splitter variable". The splitter variable attempts to separate patients in one class (e.g., Response) from those in the other class (e.g., Non-Response). The tree is grown with additional splitter variables until all terminal nodes (leaves) of the tree are purely one class or the other. This tree is then "tested" against the 1/3 of patients set aside, the "out of bag" (OOB) patients. Each OOB patient traverses the tree, going down one branch or another depending on his/her gene expression values for each splitter variable. These OOB patients are assigned a predicted class based on where they land in the tree (a vote). The entire process is repeated with new random divisions into 2/3 and 1/3 patient sets and new random gene sets for selection of splitter variables to produce additional trees and ultimately a forest. In each case a different subset of patients is used to build the tree and test its performance. At the end, each patient will have contributed to the construction of ~2/3 of all trees and been tested in the other ~1/3. Each "test" tree gives a vote for whether the patient will relapse or not relapse. The fraction of votes for relapse is an estimate of the probability of relapse and all patients will be predicted as either a relapse or non-relapse (using probability of 0.5 as the threshold). By comparing these predictions based on the OOB data to their known class, estimates of the accuracy of the overall forest can be obtained. The forest can then also be applied to independent test data or patients of unknown class (see next Figure 2).

### Figure 3. Variable importance is a feature of random forests

Now, let's proceed with the exercises. Install and load the necessary packages (if not already installed).

install.packages("randomForest")
install.packages("ROCR")
install.packages("Hmisc")
source("http://bioconductor.org/biocLite.R")
biocLite("genefilter")

library(randomForest)
library(ROCR)
library(genefilter)
library(Hmisc)

Set the working directory and file names for Input/output

setwd("/Users/ogriffit/git/biostar-tutorials/MachineLearning")
datafile="trainset_gcrma.txt"
clindatafile="trainset_clindetails.txt"
outfile="trainset_RFoutput.txt"
varimp_pdffile="trainset_varImps.pdf"
MDS_pdffile="trainset_MDS.pdf"
ROC_pdffile="trainset_ROC.pdf"
case_pred_outfile="trainset_CasePredictions.txt"
vote_dist_pdffile="trainset_vote_dist.pdf"

Next we will read in the data sets (expecting a tab-delimited file with header line and rownames). These were the outputs from the previous tutorial mentioned above. We also need to rearrange the clinical data so that it will be in the same order as the GCRMA expression data.

data_import=read.table(datafile, header = TRUE, na.strings = "NA", sep="\t")
clin_data_import=read.table(clindatafile, header = TRUE, na.strings = "NA", sep="\t")
clin_data_order=order(clin_data_import[,"GEO.asscession.number"])
clindata=clin_data_import[clin_data_order,]
data_order=order(colnames(data_import)[4:length(colnames(data_import))])+3 #Order data without first three columns, then add 3 to get correct index in original file
rawdata=data_import[,c(1:3,data_order)] #grab first three columns, and then remaining columns in order determined above
header=colnames(rawdata)
rawdata=rawdata[which(!is.na(rawdata[,3])),] #Remove rows with missing gene symbol

Next we filter out any variables (genes) that are not expressed or do not have enough variance to be informative in classification. We will first take the values and un-log2 them, then filter out any genes according to following criteria (recommended in multtest/MTP documentation): (1) At least 20% of samples should have raw intensity greater than 100; (2) The coefficient of variation (sd/mean) is between 0.7 and 10.

X=rawdata[,4:length(header)]
ffun=filterfun(pOverA(p = 0.2, A = 100), cv(a = 0.7, b = 10))
filt=genefilter(2^X,ffun)
filt_Data=rawdata[filt,]

We will assign the variables that pass this filtering process to a new data structure. Extract just the expression values from the filtered data and transpose the matrix. The latter is necessary because RandomForests expects the predictor variables (genes) to be represented as columns instead of rows. Finally, assign gene symbol as the predictor name.

#Get potential predictor variables
predictor_data=t(filt_Data[,4:length(header)])
predictor_names=c(as.vector(filt_Data[,3])) #gene symbol
colnames(predictor_data)=predictor_names

As a final step before the Random Forest classification, we have to set the variable we are trying to predict as our target variable. In this case, it is relapse status.

target= clindata[,"relapse..1.True."]
target[target==0]="NoRelapse"
target[target==1]="Relapse"
target=as.factor(target)

Finally we run the RF algorithm. NOTE: we use an ODD number for ntree. This is because when the forest/ensembl is used on test data, ties are broken randomly. Having an odd number of trees avoids this issue and makes the model fully deterministic. Also note, we will use down-sampling to attempt to compensate for unequal class-sizes (less relapses than non-relapses).

tmp = as.vector(table(target))
num_classes = length(tmp)
min_size = tmp[order(tmp,decreasing=FALSE)[1]]
sampsizes = rep(min_size,num_classes)
rf_output=randomForest(x=predictor_data, y=target, importance = TRUE, ntree = 10001, proximity=TRUE, sampsize=sampsizes, na.action = na.omit)

The final blocks of code produce various forms of output for analysis of the classifier, and final classification results. First, save the RF classifier with save(). This allows you to later load the saved model. This can be useful if you wish to rerun later parts of this script without the time-consuming model building. More importantly though it will allow you to apply the model you have built to new, independent samples for classification purposes.

save(rf_output, file="RF_model")
load("RF_model")

RandomForest calculates an importance measures for each variable. Let's save them to a new object for later use:

rf_importances=importance(rf_output, scale=FALSE)

The following lines will give an overview of the classifier's performance. Specifically, they will generate a confusion table to allow calculation of sensitivity, specificity, accuracy, etc.

confusion=rf_output$confusion sensitivity=(confusion[2,2]/(confusion[2,2]+confusion[2,1]))*100 specificity=(confusion[1,1]/(confusion[1,1]+confusion[1,2]))*100 overall_error=rf_output$err.rate[length(rf_output$err.rate[,1]),1]*100 overall_accuracy=1-overall_error class1_error=paste(rownames(confusion)[1]," error rate= ",confusion[1,3], sep="") class2_error=paste(rownames(confusion)[2]," error rate= ",confusion[2,3], sep="") overall_accuracy=100-overall_error  Next we will prepare each useful statistic for writing to an output file sens_out=paste("sensitivity=",sensitivity, sep="") spec_out=paste("specificity=",specificity, sep="") err_out=paste("overall error rate=",overall_error,sep="") acc_out=paste("overall accuracy=",overall_accuracy,sep="") misclass_1=paste(confusion[1,2], rownames(confusion)[1],"misclassified as", colnames(confusion)[2], sep=" ") misclass_2=paste(confusion[2,1], rownames(confusion)[2],"misclassified as", colnames(confusion)[1], sep=" ") confusion_out=confusion[1:2,1:2] confusion_out=cbind(rownames(confusion_out), confusion_out)  Finally, we print all of these to an output file. Note, we will be appending with multiple writes to the same file. This may generate a warning. write.table(rf_importances[,4],file=outfile, sep="\t", quote=FALSE, col.names=FALSE) write("confusion table", file=outfile, append=TRUE) write.table(confusion_out,file=outfile, sep="\t", quote=FALSE, col.names=TRUE, row.names=FALSE, append=TRUE) write(c(sens_out,spec_out,acc_out,err_out,class1_error,class2_error,misclass_1,misclass_2), file=outfile, append=TRUE)  For a simple visualization, we create a representation of the top 30 variables categorized by importance. pdf(file=varimp_pdffile) varImpPlot(rf_output, type=2, n.var=30, scale=FALSE, main="Variable Importance (Gini) for top 30 predictors") dev.off()  An MDS plot provides a sense of the separation of classes. pdf(file=MDS_pdffile) target_labels=as.vector(target) target_labels[target_labels=="NoRelapse"]="N" target_labels[target_labels=="Relapse"]="R" MDSplot(rf_output, target, k=2, xlab="", ylab="", pch=target_labels, palette=c("red", "blue"), main="MDS plot") dev.off()  A common method of assessing a classifier's performance is to create an ROC curve and calculate the area under it (AUC). We use the relapse/non-relapse vote fractions as predictive variable. The ROC curve is generated by stepping through different thresholds for calling relapse vs non-relapse. predictions=as.vector(rf_output$votes[,2])
pred=prediction(predictions,target)
#First calculate the AUC value
perf_AUC=performance(pred,"auc")
AUC=perf_AUC@y.values[[1]]
#Then, plot the actual ROC curve
perf_ROC=performance(pred,"tpr","fpr")
pdf(file=ROC_pdffile)
plot(perf_ROC, main="ROC plot")
text(0.5,0.5,paste("AUC = ",format(AUC, digits=5, scientific=FALSE)))
dev.off()

Produce a back-to-back histogram of vote distributions for Relapse and NoRelapse.

options(digits=2)
pdf(file=vote_dist_pdffile)
out <- histbackback(split(rf_output$votes[,"Relapse"], target), probability=FALSE, xlim=c(-50,50), main = 'Vote distributions for patients classified by RF', axes=TRUE, ylab="Fraction votes (Relapse)") barplot(-out$left, col="red" , horiz=TRUE, space=0, add=TRUE, axes=FALSE)
barplot(out$right, col="blue", horiz=TRUE, space=0, add=TRUE, axes=FALSE) dev.off()  Finally, we save our case predictions case_predictions=cbind(clindata,target,rf_output$predicted,rf_output\$votes)
write.table(case_predictions,file=case_pred_outfile, sep="\t", quote=FALSE, col.names=TRUE, row.names=FALSE)

After running this script you have generated a Random Forest Classifier of Relapse for breast cancer Affy data. Next, we will apply this classifier to the independent test data set. See Machine learning for cancer classification - part 3 - Predicting with a Random Forest Classifier. You also have a case_predictions file on which you can perform survival analysis, which will be the subject of a later tutorial. See Machine learning for cancer classification - part 4 - Plotting a Kaplan-Meier Curve for Survival Analysis.

r cancer classification • 65k views
ADD COMMENT
0
Entering edit mode

Hello Mr Griffith,it was as absolute pleasure going through your tutorial(which btw is a rigorous introduction to ML applications using microarray data)!

I wanted to clarify something,can you please explain to me the meaning of the below mentioned code snippet and what its doing?

data_order=order(colnames(data_import)[4:length(colnames(data_import))])+3 #Order data without first three columns, then add 3 to get correct index in original file
rawdata=data_import[,c(1:3,data_order)] #grab first three columns, and then remaining columns in order determined above

I got the order() part but why the "without first three columns" and then adding 3 to get correct index?

Same question for rawdata. Why consider the first 3 columns and then remaining in order as above?(I guess this part will be clear automatically if I understand the first part)

Thanks once again for this wonderful tutorial!

Please answer ASAP. Thanks for that too, in advance!

Shayantan

ADD REPLY
0
Entering edit mode

I'd avoid the "ASAP" part of the request - it's not really a good sign in forums.

ADD REPLY
0
Entering edit mode

@Ram I have my exams in a couple of days and hence the bad "sign" so to speak !!..Well now that you have gone through my question here,would you help by addressing the issue?

I still don't really get that part! Would love to hear from Mr Griffith though!

ADD REPLY
0
Entering edit mode

Hello,

The first three columns in the data set are non-numerical identifiers. We remove these to simplify the rest of the data-frame manipulations. Adding three to the index just makes sure gene order stays as intended.

Hope this helps!

Nick

ADD REPLY
0
Entering edit mode

I have a doubt, please correct me if I am wrong or missing anything. I found that, from the list of top 30 predictors, the gene "MLF1IP" is not present in the dataset GSE2034. As the list of predictors is generated from the original dataset only then how the above gene is not present in the dataset.

ADD REPLY
0
Entering edit mode

Dear Nicholas Spies,

I would like to ask some important questions regarding this specific part of the machine learning procedure with random forests in R, as I want to implement it to my current project. In detail, in contrast to the first part of the tutorial, my 2 datasets comprise of two colorectal cancer affymetrix datasets, but of different platform: hgu133a and hgu133plus2. Thus,

1. How I could deal with this problem, regarding the test and train set to build a classifier, in order to separate primary colon tumor samples from adjacent control samples(paired/each patient has two samples)? I have thought a methodology, which I have posted in a fork of Biostar [I'm just posting the link if anyone wants further information----Bioconductor Support group---- (https://support.bioconductor.org/p/69669/)], in which I used the inSilicoMerging package to merge the two datasets based on their common probeIDs(~22,000). I understand that this have various pitfalls(regarding batch effects), but as the package performs batch effect correction when it merges the packages-and also from the pca and plotMDS functions the samples seem to separate well. So, in this case if I proceed, how I could implement the train and test dataset? Maybe with the caret package and the function createDataPartition? Or it is irrelevant?
2. Secondly, should I reduce the number of the input for the construction of the classifier, regarding the number of the probesets? i.e use only a subgroup from DEG genes resulting from this specific statistical analysis prior the classification procedure ?

Please excuse me for the disturbance or for any naive questions, but I'm using R for the last 7 months and this tutorial is very useful and crucial to implement in my analysis, in order to compare with some other methodologies I have implement regarding the selection of a subset of possible candidates-important genes(biomarkers for further validation), any help or advise on this matter would be grateful!

Efstathios-Iason

ADD REPLY
0
Entering edit mode

Can you clarify how best splitter (gene) is chosen in a random forest? Is it based on an expression threshold? If so, how is the threshold calculated?

ADD REPLY
0
Entering edit mode

Hi Nicolas,

I asked Obi the same question, but not sure who responds quicker. I have RNA-Seq data sets. How would I load them in to run Random forest? Would I need to use a completely different approach?

Many thanks

ADD REPLY
1
Entering edit mode

please ask this as a new question and not as an answer to this post.

ADD REPLY
0
Entering edit mode

Hi, first of all thanks for this tutorial, it's done very well. I have the following suggestione for the Random Forest statement :

rf_output=randomForest(x=predictor_data, y=target, importance = TRUE, ntree = 10001, proximity=TRUE, sampsize=sampsizes, na.action = na.omit), to filter the NA values.

With this addition I've solved the problems in the Part. 3 of this tutorial.

ADD REPLY
0
Entering edit mode

Thanks for the input! It's a great thought and I will add it to the example.

ADD REPLY

Login before adding your answer.

Traffic: 2422 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6


text:
## College Algebra 7th Edition

(a) 3 (b) $x(x+1)^2$ (c) $\frac{-2x^{2}+1}{x(x+1)^{2}}$
(a) It has three terms, $\displaystyle \frac{1}{x}$, $-\frac{2}{(x+1)}$, and $-\frac{x}{(x+1)^{2}}$. (b) The least common denominator of all the terms is: $x(x+1)^{2}.$ (c) $\displaystyle \frac{1}{x}-\frac{2}{(x+1)}-\frac{x}{(x+1)^{2}}=\frac{(x+1)^{2}}{x(x+1)^{2}}-\frac{2x(x+1)}{(x+1)}-\frac{x(x)}{(x+1)^{2}}=\frac{(x+1)^{2}-2x(x+1)-x^{2}}{x(x+1)^{2}} =\frac{x^{2}+2x+1-2x^{2}-2x-x^{2}}{x(x+1)^{2}}=\frac{-2x^{2}+1}{x(x+1)^{2}}$


text:
# Expression using rational indicators and radicals and an example of a solution

Expression using rational indicators and radicals and an example of a solution
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

faldduE
An explain in raroinal exponents is a follows

Now the above expression cab be written as

This is required expression in radical form


text:
• ### Double-polarization observable G in neutral-pion photoproduction off the proton(1604.02922)

April 11, 2016 nucl-ex
This paper reports on a measurement of the double-polarization observable G in $\pi^0$ photoproduction off the proton using the CBELSA/TAPS experiment at the ELSA accelerator in Bonn. The observable G is determined from reactions of linearly-polarized photons with longitudinally-polarized protons. The polarized photons are produced by bremsstrahlung off a properly oriented diamond radiator. A frozen spin butanol target provides the polarized protons. The data cover the photon energy range from 617 to 1325 MeV and a wide angular range. The experimental results for G are compared to predictions by the Bonn-Gatchina (BnGa), J\"ulich-Bonn (J\"uBo), MAID and SAID partial wave analyses. Implications of the new data for the pion photoproduction multipoles are discussed.
• ### Measurement of double polarisation asymmetries in $\omega$-photoproduction(1504.02221)

Sept. 1, 2015 nucl-ex
The first measurements of the beam-target-helicity-asymmetries $E$ and $G$ in the photoproduction of $\omega$-mesons off protons at the CBELSA/TAPS experiment are reported. $E$ ($G$) was measured using circularly (linearly) polarised photons and a longitudinally polarised target. $E$ was measured over the photon energy range from close to threshold ($E_\gamma = 1108$~MeV) to $E_\gamma = 2300$~MeV and $G$ at a single energy interval of $1108 < E_\gamma <1300$~MeV. Both measurements cover the full solid angle. The observables $E$ and $G$ are highly sensitive to the contribution of baryon resonances, with $E$ acting as a helicity filter in the $s$-channel. The new results indicate significant $s$-channel resonance contributions together with contributions from $t$-channel exchange processes. A partial wave analysis reveals strong contributions from the partial waves with spin-parity $J^P=3/2^+, 5/2^+$, and $3/2^-$.
• ### The polarization observables T, P, and H and their impact on $\gamma p \to p\pi^0$ multipoles(1506.06226)

June 20, 2015 nucl-ex
Data on the polarization observables T, P, and H for the reaction $\gamma p\to p\pi^0$ are reported. Compared to earlier data from other experiments, our data are more precise and extend the covered range in energy and angle substantially. The results were extracted from azimuthal asymmetries measured using a transversely polarized target and linearly polarized photons. The data were taken at the Bonn electron stretcher accelerator ELSA with the CBELSA/TAPS detector. Within the Bonn-Gatchina partial wave analysis, the new polarization data lead to a significant narrowing of the error band for the multipoles for neutral-pion photoproduction.
• ### Constraining nova observables: direct measurements of resonance strengths in 33S(p,\gamma)34Cl(1309.3543)

Sept. 13, 2013 nucl-ex, astro-ph.SR
The 33S(p,\gamma)34Cl reaction is important for constraining predictions of certain isotopic abundances in oxygen-neon novae. Models currently predict as much as 150 times the solar abundance of 33S in oxygen-neon nova ejecta. This overproduction factor may, however, vary by orders of magnitude due to uncertainties in the 33S(p,\gamma)34Cl reaction rate at nova peak temperatures. Depending on this rate, 33S could potentially be used as a diagnostic tool for classifying certain types of presolar grains. Better knowledge of the 33S(p,\gamma)34Cl rate would also aid in interpreting nova observations over the S-Ca mass region and contribute to the firm establishment of the maximum endpoint of nova nucleosynthesis. Additionally, the total S elemental abundance which is affected by this reaction has been proposed as a thermometer to study the peak temperatures of novae. Previously, the 33S(p,\gamma)34Cl reaction rate had only been studied directly down to resonance energies of 432 keV. However, for nova peak temperatures of 0.2-0.4 GK there are 7 known states in 34Cl both below the 432 keV resonance and within the Gamow window that could play a dominant role. Direct measurements of the resonance strengths of these states were performed using the DRAGON recoil separator at TRIUMF. Additionally two new states within this energy region are reported. Several hydrodynamic simulations have been performed, using all available experimental information for the 33S(p,\gamma)34Cl rate, to explore the impact of the remaining uncertainty in this rate on nucleosynthesis in nova explosions. These calculations give a range of ~ 20-150 for the expected 33S overproduction factor, and a range of ~ 100-450 for the 32S/33S ratio expected in ONe novae.
• ### High-Precision Measurement of the 19Ne Half-Life and Implications for Right-Handed Weak Currents(1206.5742)

June 26, 2012 nucl-ex
We report a precise determination of the 19Ne half-life to be $T_{1/2} = 17.262 \pm 0.007$ s. This result disagrees with the most recent precision measurements and is important for placing bounds on predicted right-handed interactions that are absent in the current Standard Model. We are able to identify and disentangle two competing systematic effects that influence the accuracy of such measurements. Our findings prompt a reassessment of results from previous high-precision lifetime measurements that used similar equipment and methods.


text:
# Simple Choice-Dialog like the auto-completion popup

What I want is pretty simple, nevertheless, after half an hour I have only unsatisfying solutions here. Let me ask you who might work more often with Mathematica's GUI elements:

Is there a way to implement a dialog in Mathematica which works in general like the autocompletion popup.

The dialog doesn't have to popup automatically but it should have the following features:

• it is a fixed list of entries, where the first entry is always selected and you can use the arrow keys to navigate up and down
• on Enter or Esc the dialog closes where in the first case, some identifier with the selected entry is returned
• I can use a unique "short-key" which lets me directly select and return one of the entries. So for instance if my list of choices is {"Module","Block","With"} I could use e.g. m, b and w to select the corresponding entry.

I have played with various dialogs, button bars and EventHandler without luck. Bevor I investigate further, I thought asking is probably the better choice.

• I once created a nice solution for this problem for one of my customers. I know that it was a rather lenghty function which took me hours of work. Thus, I think you are not underestimating the complexity of the problem. – Ariel Sepulveda Jul 29 '14 at 21:15
• @ArielSepulveda I do have a hand-crafted list-dialog-clickedy-clack too for my symbol information palette but this lacks of the short-cuts and arrow keys. You always have to click. Additionally, and I haven't mentioned this here, I would like the dialog to popup at cursor (not mouse!) position. This seems impossible to achieve as far as I can tell. As always, if you want to do a real application with the dynamic UI elements it is never a one-line like advertised in the million toy-demonstrations. – halirutan Jul 29 '14 at 21:24
• I'm not sure of what you mean by popup at cursor but maybe something can be done by means of InputField. You can move from one InputField to the next by using Tab, once you get to the desired field, typing the search string may be enough to dynamically popup the matches as a list and then use the arrow keys to navigate to the desired one, and finally, conclude the selection with a "ReturnKeyDown" which will be "collected" by the EventHandler. Thus, you may have to end up combining Dynamic with Button and EventHandler. Complicated? Yes, but maybe not impossible ;) – Ariel Sepulveda Jul 29 '14 at 21:45
• @ArielSepulveda With popup at cursor I mean the behavior the autocompletion popup shows: It appears exactly beneath your current cursor position where you type. – halirutan Jul 29 '14 at 23:28
• @halirutan At last WC, WRI devs (don't remember who exactly) said that those floating gui elements are going to be introduced. No specific date/time was mentioned so I'd not wait for it though. – Kuba Jan 19 '15 at 21:03

### Edit

Once again b3m2a1 provided more detailed information about a FE's feature so I have to retract my claim that it is not worth an effort to create a popup on cursor position as opposed to e.g. in the corner of the notebook.

### Main

The following answer is closely related to Live code templates I'm working on in a free time.

I will outline two alternative methods, attached cell vs frameless palette. (the linked topic uses the former one but without attaching on a cursor position)

### tl;dr;

Make sure you saved your work, this is a rough implementation and the "Cell" approach uses an undocumented AttachedCell.

• Run code from the last section,

• run testPopup["Palette"]

• hit Ctrl+1 to interact with menu.

This one is not on cursor position because it is tough :) this one is:

• testPopup["Cell"]

### Cell vs. Palette

• Palette is not clipped by a parent notebook what is very convenient when the cursor is close to the bottom/right edge or the menu is not small.

• Palette notebook is documented

• AttachedCell can be placed directly on a cursor position, thanks to an UndocumentedGetSelectionPacket. It is not easy with Palette because Undocu... does not account on DockedCells and additionaly we need to do WindowMargins arithmetic.

### Cursor position

FrontEndExecute @ FrontEndUndocumentedGetSelectionPacket @ InputNotebook[]

its "VirtualSelectionRectangle" value is a cursor position with respect to the bottom left edge of the very bottom docked cell (or a nb menu).

### Key events

Whatever wrapper you use the key point is to create a DynamicModule that will temporarily overwrite parent notebook's NotebookEventActions on Initialization and will revert old settings on Deinitialization (you thought you will never use this opition, didn't you?).

Once Arrows/Enter/Esc are overwritten there is no problem in "KeyDown" event and check if an event key isn't a member of defined shortcuts.

### Demo code

CenterToParent is taken from How to center a dialog with respect to a parent notebook

testPopup[type:"Cell"|"Palette":"Cell"]:=CreateDocument[{}
, WindowTitle -> type <> " popup menu"
, StyleDefinitions -> Notebook[{
Cell[StyleData[StyleDefinitions -> "Default.nb"]]
, Cell[StyleData["Notebook"]
, NotebookEventActions -> {{"MenuCommand", "InsertNewGraphic"}:>openPopup[type]} (*Ctrl+1*)
]
}]
];

items = {
<|"lbl"->"item 1","action":>NotebookWrite[InputNotebook[], "item1"],"shortkey" -> "m"|>,
<|"lbl"->"item 2","action":>NotebookWrite[InputNotebook[], "item2"],"shortkey" -> "k"|>,
<|"lbl"->"item 2","action":>NotebookWrite[InputNotebook[], "item3"],"shortkey" -> "l"|>
};

openPopup["Palette"]:= NotebookPut @ CenterToParent @ Notebook[
List @ Cell[BoxData @ ToBoxes @ popupMenu["Palette"]
, CellFrameMargins->{{0, 0}, {0, 0}}
, CellMargins->{{0, 0}, {0, 0}}
]
, StyleDefinitions->"Dialog.nb"
, WindowClickSelect->False
, WindowFloating->True
, WindowFrame->"Frameless"
, WindowSize->All
, Background->LightBlue
, WindowElements->{}
, WindowFrameElements->{}
];

openPopup["Cell"] := Module[{sel,fromTop, fromLeft}
, Catch[
sel = FrontEndExecute@FrontEndUndocumentedGetSelectionPacket@
InputNotebook[]
; If[
MatchQ[sel, KeyValuePattern[{"CellSelectionType" -> "ContentSelection", "SelectionType" -> "CursorRight"}]]
, {fromLeft,fromTop} = Lookup[sel, "VirtualSelectionRectangle", {{0,0},{0,0}}][[All, 1]]
, Beep[];Throw@\$Canceled
]
; MathLinkCallFrontEnd[
FrontEndAttachCell[
EvaluationNotebook[]
, Cell @ BoxData @ ToBoxes @ popupMenu["Cell"]
, {Offset[{-fromLeft,-fromTop},0], {Left,Top}}
, {Left,Top}
, "ClosingActions"->{ "OutsideMouseClick" }
]
]
]
];

{item=1,thisObject, parentObject, menuClose, items = items, itemsLength = Length@items}
, Table[With[{i=i},
EventHandler[#, "MouseEntered":>(item = i)]& @ Button[
Style[
StringTemplate["lbl (shortkey)"]@items[[i]], Bold, FontColor-> Dynamic@If[item==i,Darker@Red,Darker@Green]]
, FrameMargins->15
, ImageMargins->0
, Appearance->FrontEndResource["FEExpressions","GrayNinePatchAppearance"]
]]
, {i, itemsLength}
]//Column[#,Spacings->0]&
, Initialization:>(
If[
type === "Palette"
,
thisObject = EvaluationNotebook[];
,
thisObject = EvaluationCell[];
];
parentObject = InputNotebook[];

CurrentValue[parentObject, NotebookEventActions] = {
"UpArrowKeyDown":>(item=Mod[item-1,itemsLength,1])
, "DownArrowKeyDown":>(item=Mod[item+1,itemsLength,1])
, "ReturnKeyDown" :> (items[[item, 2]]; menuClose[])
, "KeyDown" :> If[
MemberQ[items[[;;, "shortkey"]], CurrentValue["EventKey"]]
, (#action& /@ Select[items, #shortkey === CurrentValue["EventKey"]&]);menuClose[]
]
}
)
, Deinitialization:>(
CurrentValue[parentObject,NotebookEventActions]=Inherited
)
]

CenterToParent::usage =  "CenterToParent[DialogInput[...]] etc, will make the dialog centered with respect to the parent notebook";

CenterToParent // Attributes = {HoldFirst};

CenterToParent[ dialog_[whatever__, opts : OptionsPattern[]]  ] := With[
{apc = AbsoluteCurrentValue}
, With[
{ parentCenter = Transpose @ {
apc[WindowMargins][[;; , 1]] + .5 apc[ WindowSize]
, {Automatic, Automatic}
}
}
, dialog[
whatever
, NotebookDynamicExpression :> Refresh[
SetOptions[
EvaluationNotebook[]
, WindowMargins -> (parentCenter - Transpose[{.5 apc[WindowSize], {0, 0}}])
, NotebookDynamicExpression -> None
]
, None
]
, opts
]
]
];

• I forgot to update that answer, but AttachedCell can actually take an Offset spec, so it can be in arbitrary directions. I'll get to that later today. In the meantime you can see my implementation of a top-level attacher here which will hopefully make it clearer how this works. – b3m2a1 Jan 29 '18 at 18:12
• Thanks, I will update the answer. I was playing with Offset but after couple of FE crashes and forgetting about coordinates orientation I wrongly assumed it does not work. Thanks again. – Kuba Jan 29 '18 at 20:39