text:
# Spin-Orbit Calculations in QMC¶

## Introduction¶

In order to introduce relativistic effects in real materials, in principle the full Dirac equation must be solved where the resulting wave function is a four-component spinor. For the valence electrons that participate in chemistry, the single particle spinors can be well approximated by two-component spinors as two of the components are negligible. Note that this is not true for the deeper core electrons, where all four components contribute. In light of this fact, relativistic pseudopotentials have been developed to remove the core electrons while providing an effective potential for the valence electrons [DC12]. This allows relativistic effects to be studied in QMC methods using two-component spinor wave functions.

In QMCPACK, spin-orbit interactions have been implemented following the methodology described in [MZG+16] and [MBM16]. We briefly describe some of the details below.

## Single-Particle Spinors¶

The single particle spinors used in QMCPACK take the form

(63)$\begin{split} \phi(\mathbf{r},s) &=& \, \phi^\uparrow(\mathbf{r}) \chi^\uparrow(s) + \phi^{\downarrow}(\mathbf{r})\chi^\downarrow(s) \\ &=& \, \phi^\uparrow(\mathbf{r}) e^{i s} + \phi^{\downarrow}(\mathbf{r}) e^{-i s}\:,\end{split}$

where $$s$$ is the spin variable and using the complex spin representation. In order to carry out spin-orbit calculations in solids, the single-particle spinors can be obtained using Quantum ESPRESSO. After carrying out the spin-orbit calculation in QE (with flags noncolin = .true., lspinorb = .true., and a relativistic .UPF pseudopotential), the spinors can be obtained by using the converter convertpw4qmc:

convertpw4qmc data-file-schema.xml

where the data-file-schema.xml file is output from your QE calculation. This will produce an eshdf.h5 file which contains the up and down components of the spinors per k-point.

## Trial Wavefunction¶

Using the generated single particle spinors, we build the many-body wavefunction in a similar fashion to the normal non-relativistic calculations, namely

(64)$\Psi_T(\mathbf{R},\mathbf{S}) = e^J \sum\limits_\alpha c_\alpha \det_\alpha\left[ \phi_i(\mathbf{r}_j, s_j) \right]\:,$

where we now utilize determinants of spinors, as opposed to the usual product of up and down determinants. An example xml input block for the trial wave function is show below:

Listing 58 wavefunction specification for a single determinant trial wave function
<?xml version="1.0"?>
<qmcsystem>
<wavefunction name="psi0" target="e">
<sposet_builder name="spo_builder" type="bspline" href="eshdf.h5" tilematrix="100010001" twistnum="0" source="ion0" size="10">
<sposet type="bspline" name="myspo" size="10">
<occupation mode="ground"/>
</sposet>
</sposet_builder>
<determinantset>
<slaterdeterminant>
<determinant id="det" group="u" sposet="myspo" size="10"/>
</slaterdeterminant>
</determinantset>
<jastrow type="One-Body" name="J1" function="bspline" source="ion0" print="yes">
<correlation elementType="O" size="8" cusp="0.0">
<coefficients id="eO" type="Array">
</coefficients>
</correlation>
</jastrow>
<jastrow type="Two-Body" name="J2" function="bspline" print="yes">
<correlation speciesA="u" speciesB="u" size="8">
<coefficients id="uu" type="Array">
</coefficients>
</correlation>
</jastrow>
</wavefunction>
</qmcsystem>

We note that we only specify an “up” determinant, since we no longer need a product of up and down determinants. In the Jastrow specification, we only need to provide the jastrow terms for the same spin as there is no longer a distinction between the up and down spins.

We also make a small modification in the particleset specification:

Listing 59 specification for the electron particle when performing spin-orbit calculations
<particleset name="e" random="yes" randomsrc="ion0" spinor="yes">
<group name="u" size="10" mass="1.0">
<parameter name="charge"              >    -1                    </parameter>
<parameter name="mass"                >    1.0                   </parameter>
</group>
</particleset>

Note that we only provide a single electron group to represent all electrons in the system, as opposed to the usual separation of up and down electrons. The additional keyword spinor=yes is the only required keyword for spinors. This will be used internally to determine which movers to use in QMC drivers (e.g. VMCUpdatePbyP vs SOVMCUpdatePbyP) and which SPOSets to use in the trial wave function (spinors vs. normal orbitals)

note: In the current implementation, spinor wavefunctions are only supported at the single determinant level. Multideterminant spinor wave functions will be supported in a future release.

## QMC Methods¶

In this formalism, the spin degree of freedom becomes a continuous variable similar to the spatial degrees of freedom. In order to sample the spins, we introduce a spin kinetic energy operator

(65)$T_s = \sum_{i=1}^{N_e} -\frac{1}{2\mu_s} \left[ \frac{\partial^2}{\partial s_i^2} + 1\right]\:,$

where $$\mu_s$$ is a spin mass. This operator vanishes when acting on an arbitrary spinor or anti-symmetric product of spinors due to the offset. This avoids any unphysical contribution to the local energy. However, this does contribute to the Green’s function in DMC,

(66)$G(\mathbf{R}' \mathbf{S}' \leftarrow \mathbf{R}\mathbf{S}; \tau, \mu_s) \propto G(\mathbf{R}'\leftarrow\mathbf{R}; \tau) \exp\left[ -\frac{\mu_s}{2\tau}\left| \mathbf{S}' - \mathbf{S} - \frac{\tau}{\mu_s}\mathbf{v}_{\mathbf{S}}(\mathbf{S})\right|^2\right] \:,$

where $$G(\mathbf{R}'\leftarrow\mathbf{R}; \tau)$$ is the usual Green’s function for the spatial evolution and the spin kinetic energy operator introduces a Green’s function for the spin variables. Note that this includes a contribution from the spin drift $$\mathbf{v}_{\mathbf{S}}(\mathbf{S}) = \nabla_{\mathbf{S}} \ln \Psi_T(\mathbf{S})$$.

In both the VMC and DMC methods, there are no required changes to a typical input

<qmc method="vmc/dmc">
<parameter name="steps"    >    50   </parameter>
<parameter name="blocks"   >    50   </parameter>
<parameter name="walkers"  >    10   </parameter>
<parameter name="timestep" >  0.01   </parameter>
</qmc>

Whether or not spin moves are used is determined internally by the spinor=yes flag in particleset.

By default, the spin mass $$\mu_s$$ (which controls the rate of spin sampling relative to the spatial sampling) is set to 1.0. This can be changed by adding an additional parameter to the QMC input

<parameter name="spinMass" > 0.25 </parameter>

A larger/smaller spin mass corresponds to slower/faster spin sampling relative to the spatial coordinates.

## Spin-Orbit Effective Core Potentials¶

The spin-orbit contribution to the Hamiltonian can be introduced through the use of Effective Core Potentials (ECPs). As described in [MBM16], the relativistic (semilocal) ECPs take the general form

(67)$W^{\rm RECP} = W_{LJ}(r) + \sum_{\ell j m_j} W_{\ell j}(r) | \ell j m_j \rangle \langle \ell j m_j | \:,$

where the projectors $$|\ell j m_j\rangle$$ are the so-called spin spherical harmonics. An equivalent formulation is to decouple the fully relativistic effective core potential (RECP) into averaged relativistic (ARECP) and spin-orbit (SORECP) contributions:

(68)$\begin{split}W^{\rm RECP} &=& \, W^{\rm ARECP} + W^{\rm SOECP} \\ W^{\rm ARECP} &=& \, W^{\rm ARECP}_L(r) + \sum_{\ell m_\ell} W_\ell^{ARECP}(r) | \ell m_\ell \rangle \langle \ell m_\ell| \\ W^{\rm SORECP} &=& \sum_\ell \frac{2}{2\ell + 1} \Delta W^{\rm SORECP}_\ell(r) \sum\limits_{m_\ell,m_\ell'} |\ell m_\ell\rangle \langle \ell m_\ell | \vec{\ell} \cdot \vec{s} | \ell m_\ell' \rangle \langle \ell m_\ell'|\:.\end{split}$

Note that the $$W^{\rm ARECP}$$ takes exactly the same form as the semilocal pseudopotentials used in standard QMC calculations. In the pseudopotential .xml file format, the $$W^{\rm ARECP}_\ell(r)$$ terms are tabulated as usual. If spin-orbit terms are included in the .xml file, the file must tabulate the entire radial spin-orbit prefactor $$\frac{2}{2\ell + 1}\Delta W^{\rm SORECP}_\ell(r)$$. We note the following relations between the two representations of the relativistic potentials

(69)$\begin{split}W^{\rm ARECP}_\ell(r) &=& \frac{\ell+1}{2\ell+1} W^{\rm RECP}_{\ell,j=\ell+1/2}(r) + \frac{\ell}{2\ell+1} W^{\rm RECP}_{\ell,j=\ell-1/2}(r) \\ \Delta W^{\rm SORECP}_\ell(r) &=& W^{\rm RECP}_{\ell,j=\ell+1/2}(r) - W^{\rm RECP}_{\ell,j=\ell-1/2}(r)\end{split}$

The structure of the spin-orbit .xml is

<?xml version="1.0" encoding="UTF-8"?>
<pseudo>
<grid ... />
<semilocal units="hartree" format="r*V" npots-down="4" npots-up="0" l-local="3" npots="2">
<vps l="s" .../>
<vps l="p" .../>
<vps l="d" .../>
<vps l="f" .../>
<vps_so l="p" .../>
<vps_so l="d" .../>
</semilocal>
</pseudo>

This is included in the Hamiltonian in the same way as the usual pseudopotentials. If the <vps_so> elements are found, the spin-orbit contributions will be present in the calculation. By default, the spin-orbit terms will be included in the local energy. In order to accumulate the spin-orbit energy, but exclude it from the local energy (and therefore will not be propogated into the walker weights in DMC for example), the physicalSO flag should be set to no in the Hamiltonian input. A typical application will include the SOC terms in the local energy, and an example input block is given as

<hamiltonian name="h0" type="generic" target="e">
<pairpot name="ElecElec" type="coulomb" source="e" target="e" physical="true"/>
<pairpot name="IonIon" type="coulomb" source=ion0" target="ion0" physical="true"/>
<pairpot name="PseudoPot" type="pseudo" source="i" wavefunction="psi0" format="xml" algorithm="non-batched">
<pseudo elementType="Pb" href="Pb.xml"/>
</pairpot>
</hamiltonian>

The contribution from the spin-orbit will be printed to the .stat.h5 and .scalar.dat files for post-processing. An example output is shown below

LocalEnergy           =           -3.4419 +/-           0.0014
Variance              =            0.1132 +/-           0.0013
Kinetic               =            1.1252 +/-           0.0027
LocalPotential        =           -4.5671 +/-           0.0028
ElecElec              =            1.6881 +/-           0.0025
LocalECP              =           -6.5021 +/-           0.0062
NonLocalECP           =            0.3286 +/-           0.0025
LocalEnergy_sq        =           11.9601 +/-           0.0086
SOECP                 =          -0.08163 +/-           0.0003

The NonLocalECP represents the $$W^{\rm ARECP}$$, SOECP represents the $$W^{\rm SORECP}$$, and the sum is the full $$W^{\rm RECP}$$ contribution.

Note that for now, the default “batched” non-local pseudopotential evaluation is not compatible with dynamical spin QMC calculations. Therefore, the specification of algorithm=”non-batched” in all pseudopotential blocks is required.

DC12

Michael Dolg and Xiaoyan Cao. Relativistic pseudopotentials: their development and scope of applications. Chemical Reviews, 112(1):403–480, 2012. PMID: 21913696. URL: https://doi.org/10.1021/cr2001383, arXiv:https://doi.org/10.1021/cr2001383, doi:10.1021/cr2001383.

MBM16(1,2)

Cody A. Melton, M. Chandler Bennett, and Lubos Mitas. Quantum monte carlo with variable spins. The Journal of Chemical Physics, 144(24):244113, 2016. URL: https://doi.org/10.1063/1.4954726, arXiv:https://doi.org/10.1063/1.4954726, doi:10.1063/1.4954726.

MZG+16

Cody A. Melton, Minyi Zhu, Shi Guo, Alberto Ambrosetti, Francesco Pederiva, and Lubos Mitas. Spin-orbit interactions in electronic structure quantum monte carlo methods. Phys. Rev. A, 93:042502, Apr 2016. URL: https://link.aps.org/doi/10.1103/PhysRevA.93.042502, doi:10.1103/PhysRevA.93.042502.


text:
Simple HEAT TRANSFER problem

I need to use the equation below ( thermal resistance for convection)

R= 1/hA

but I am not given an Area, I am only given 4 meters as a thickness. how do I find A to use for the equation to solve for R.

Mapes

format: plain


text:
# Integral Solutions

$abcde=1050$

and a, b, c, d, e are positive integers. How many ordered tuples $$(a, b, c, d, e)$$ exist?

Extra Credit: How many unordered sets $${a, b, c, d, e}$$ exist?

Extra Credit: How many ordered tuples $$(a, b, c, d, e)$$ exist such that a≠b≠c≠d≠e?

Unrelated Credit: Solve the Aunty's Teacups problem

×


text:
# Projection matrix

[/B]

## The Attempt at a Solution

The solution is obviously given, but I don't really understand what is done there. What method is being used? so I can understand, because i see how they attained v, but then that vector normalised is not correct is it?

#### Attachments

• 40756682_1595386137274940_7144466539691900928_n.png
34 KB · Views: 493

## Answers and Replies

StoneTemplePython
Gold Member
You (and we) need the Relevant Equations filled out.

What is a Projection Matrix? What kinds of properties does it have that we can take for granted?

You (and we) need the Relevant Equations filled out.

What is a Projection Matrix? What kinds of properties does it have that we can take for granted?
Don't worry, I learned how to solve it now. since you can find the projection matrix pretty easily then you just plug in the values from the given vector, here W (unit vector of v) the squares cancel the square roots and you're left with that matrix in solution P. But i was wondering how do you add a matrix into the text?

Last edited by a moderator:
StoneTemplePython


text:
It is well known that adding unrestricted kind polymorphism to the higher-order polymorphic lambda calculus, a.k.a. System $$F_\omega$$, leads to logically inconsistent paradoxes. For those in dependently typed theorem proving community, this is non of their concern, since dependently typed proof assistants are usually based on predicative calculus with stratified universes. However, there is an alternative approach that has not been well explored yet.

Consider taking an alternative approach of starting from a more traditional functional language based on impredicative polymorphism and turning that into a theorem proving system. For instance consider a certain subset of Haskell with GHC extensions such as RankNTypes and ImpredicativeTypes (after all, core of GHC is an extension of $$F_\omega$$ ), and trying to carve out a logically consistent language. This is exactly the motivation of my Ph.D. thesis, and its resulting artifact is the Nax language. To make the long story short, we should be able to have a logically consistent subset of say Haskell with GHC extension including GADTs and PolyKind. The benefit of such design is that we can reuse all the facilities that have already been built around functional languages like Haskell, which has far more sophisticated and well-optimized compilers than most theorem proving systems.

If we take this route, we should figure out a safe way to extend impredicative polymorphism with a restricted form of kind polymorphism. I believe that extending $$F_\omega$$ with Rank 1 polymorphic kind bindings for finite number of globally defined type constructor variables is safe. That is, the resulting calculus with this extension is logically consistent. Proof of logical consistency of this extended calculus should be quite straightforward by mapping the extended calculus back into $$F_\omega$$ by inlining.

Here is the syntax of the extended calculus: $$\sigma ::= \kappa \mid \forall \chi.\kappa$$ $$\kappa ::= \chi \mid * \mid \kappa \to \kappa’$$ $$A, B, F, G ::= X \mid A \to B \mid \lambda X^{\kappa}.F \mid F~G \mid \forall X^{\kappa}.B$$ $$\Sigma ::= \cdot \mid T^\sigma,\Sigma$$ $$\Gamma ::= \cdot \mid X^{\kappa} \mid x:A$$ $$t, r, s ::= x \mid \lambda x.t \mid r~s$$

A type constructor name $$T$$ is no different than a type variable $$X$$. It is just a notional convention to emphasize that the variable stands for a globally defined name for a type constructor. From a list of globally defined type constructors $$T_1 = F_1, T_2 = F_2, \ldots, T_n = F_n$$ a global context $$\Sigma$$ can be obtained such that $$\Sigma = T_1^{\sigma_1}, T_2^{\sigma_2}, \ldots, T_n^{\sigma_n}$$ Each $$\sigma_i$$ is a polymorphic kind of $$F_i$$. For instance, the polymorphic kind scheme of $$F_1 = \lambda X^{\chi}.X$$ is $$\sigma_1 = \forall \chi.\chi \to \chi$$.

For simplicity, let us consider just one global definition where $$T_1 = F_1$$. Assuming $$F_1$$ is well kinded, we get $$\Sigma = T_1^{\sigma_1]}$$. In the derivation tree of a typing judgment $$T_1^{\sigma_1};\Gamma \vdash t : A$$, we inline each occurrence of $$T_1$$ with an instantiation of its definition $$F_1$$, instantiating all the free kind variables in $$F_1$$ appropriately for each occurrence. For instance, if we had $$F_1 = \lambda X^{\chi}.X$$, we might instantiate it to $$\lambda X^{*}.X$$, $$\lambda X^{ * \to * }.X$$, or any appropriate instantiation of $$\chi$$ as needed. Once we have inlined every occurrence of $$T_1$$, the global context $$\Sigma$$ becomes irrelevant. Therefore, we can simply ignore $$\Sigma$$, and the resulting derivation tree is exactly the derivation tree for a typing judgment in $$F_\omega$$.

Generalizing the inlining for $$n$$ definitions is not so hard. The only additional thing to consider is that the previously defined type constructor names can be used in the latter definitions. Consider $$T_1 = F_1, T_2 = F_2, \ldots, T_n = F_n$$. The first name $$T_1$$ can appear in any of $$F_2, \ldots, F_n$$. So, inlining should be performed in a cascading manner starting from $$T_1$$, inlining inside $$\Sigma$$ as well as other parts of the derivation tree.

Next step is to generalize this idea for System $$F_i$$ which extends System $$F_\omega$$ with erasable type indices. Here, this will get more complicated because type variables and term-index variables can appear in kinds as well as kind variables.


text:
# The 2009 Europhysics Conference on High Energy Physics

Jul 16 – 22, 2009
Kraków, Poland
Europe/Warsaw timezone

## Coupled channel description for X(3872) and other XYZ mesons

Jul 18, 2009, 11:55 AM
20m
Exhibition room B (Kraków, Poland)

### Exhibition room B

#### Kraków, Poland

The Auditorium Maximum of the Jagiellonian University 33 Krupnicza Street 31-123 Kraków

### Speaker

Mr Pablo G. Ortega (University of Salamanca)

### Description

In the last years a number of exciting discoveries of new hadron states have challenged our description of the hadron spectroscopy. Among the several charmonium states (X(3940), Y(3940), Z(3930)) the most mysterious one is the well established $X(3872)$. It was first discovered by the Belle Collaboration in the $J/\psi \pi \pi$ invariant mass spectrum of the decay $B\rightarrow K^+ \pi^+\pi^-J/\psi$. Its mass and relative decay rates outlines a puzzling structure. The $\gamma J/\psi$ and $\gamma \psi'$ decay rates suggest a $c\bar c$ structure whereas the ratio $X(3872)\to \pi^+ \pi^- \pi^0 J/\psi$ to $X(3872)\rightarrow \pi^+\pi^-J/\psi$ which is almost 1 indicates a large isospin violation incompatible with a traditional charmonium assumption. On the other hand the $X(3872)$ mass is difficult to reproduce by the standard quark models. The state appears to be too heavy for a $1D$ charmonium state and too light for a $2P$ charmonium one. In this work, we have performed a coupled channel calculation of the $1^{++}$ sector including both $c\bar c$ and $DD^*$ states. The calculation was done in the framework of the constituent quark model of Ref. [1]. Two and four quark configurations are coupled using the $^3P_0$ model. All the parameters are taken from the previous calculation in the $c\bar c$ sector including the $\gamma$ parameter of the $^3P_0$ model [2], so the calculation is parameter free. We first perform an isospin symmetric calculation including $^3 S_1$ and $^3D_1$ $DD^*$ partial waves. If we neglect the coupling to $c\bar c$ states we don't get a bound state for the $DD^*$ molecule in the $1^{++}$ channel, neither in the $I=0$ nor in the $I=1$ channels. When the coupling to $c\bar c$ states is included we find an almost pure $c\bar c(1 ^3P_1)$ state with mass $3467\,MeV$ which we identify with the $\chi_{c_1}(1P)$ and two states with significant molecular admixture. One of them with mass $3865\,MeV$ is almost a $DD^*$ molecule bound by the coupling to the $c\bar c$ states. The second one, with mass $3936\,MeV$, is a $c\bar c(2 ^3P_1)$ with sizable $DD^*$ component. We assign the first state to the $X(3872)$, being the second one a candidate to the $X(3940)$. When the mass difference between neutral and charged states is included a large $D^0 {D^*}^0$ component is found which dominates for large distances and breaks isospin symmetry in the physical state. If we extend the same model to other XYZ charmonium states we get a $2^{++}$ at M=3968 MeV which can be identified with the Z(3930), but we do not find any candidate for the Y(3940). As a summary, we have shown that the $X(3872)$ emerges in a constituent quark model calculation as a mixed state of a $DD^*$ molecule and $\chi_{c_1}(2P)$ state. This framework may explain simultaneously the isospin violation showed by the experimental data and the radiative decay rates. We interpret the $X(3940)$ as the $\chi_{c_1}(2P)$ state with a significant $DD^*$ component. Within the same model the Z(3930) appears as a $2^{++}$ charmonium state. [1] J. Vijande, F. Fern\'andez, and A. Valcarce, J. Phys G {\bf 31}, 481 (2005). [2] J. Segovia, A.M. Yasser, D. R. Entem, F. Fernandez Phys. Rev. D {\bf 78}, 114033 (2008).

### Primary author

Prof. Francisco Fernandez (University of Salamanca)

### Co-authors

Mr Jorge Segovia (University of Salamanca) Mr Pablo G. Ortega (University of Salamanca)

 Slides


text:
# The Glossary of Human Computer Interaction

by

The task-artifact cycle (artifact can also be spelled artefact) captures the idea that tasks and artifacts coevolve (Carroll et al. 1991). The cyclical relationship between the two can be described as follows: A given task sets requirements for the design of an artifacts to help an individual perform the task. The resulting artifact, in turn, creates new or uexpected possibilities or pose new constraints on the performance of the task. These possiblities and/or constraints often suggest a revision of the original task for which the artefact was made. The new task sets new requirements for the redesign of the artifact and so on and so on (de Lëon 1999). The task-artifact cycle is in other words an iterative process of continuous, mutually dependent development between task and artifact, a process that will never reach an optimum state.


text:
# Linear oblique asymptote

Coco12

## Homework Statement

what is the linear oblique asymptote of (x^5+x^3+2)/(x^4-1)
?

## Homework Equations

x-a/p(x) = q(x) +remainder

## The Attempt at a Solution

I put in all the placeholders for the divisor and the numerator and got x as the equation for the linear oblique asymptote?? Is that right??

Homework Helper
We would let

$$\frac{x^5+x^3+2}{x^4-1}\equiv \frac{(ax+b)(x^4-1)+p(x)}{x^4-1} = ax+b + \frac{p(x)}{x^4-1}$$

Where p(x) is a cubic polynomial or less (doesn't matter what it is exactly).

If we expanded (ax+b)(x4-1) then we get

$$ax^5+bx^4-ax-b$$

But we ignore the -ax-b term because that will be a part of p(x) which we've already said we don't care about. So we want the constant a to be chosen such that $ax^5=x^5$ since the coefficient of $x^5$ on the LHS must be equal to the RHS, hence a=1, and b must be chosen such that $bx^4=0$ for the same reason, hence b=0.

But we ignore the -ax-b term because that will be a part of p(x) which we've already said we don't care about.

Coco12
Is the answer that I got correct? Thanks for taking the time to answer. I know how to do it just wondering if it's correct

#### Attachments

• image.jpg
2.1 KB · Views: 333
Homework Helper
Yes, y= x is the "liner oblique asymptote".

Mentor
Is the answer that I got correct? Thanks for taking the time to answer. I know how to do it just wondering if it's correct
No, this isn't correct. It's the equation of the rational function you started with.

To find the oblique asymptote, either do what Mentallic suggested or carry out the long division to get x + a proper rational function. In a proper rational function, the degree of the numerator is less than that of the denominator.

Coco12
Yes, y= x is the "liner oblique asymptote".

Ok thank you


text:
Find all School-related info fast with the new School-Specific MBA Forum

 It is currently 30 May 2016, 09:47

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

# Calling All Fall 2012 Consortium Applicants!

Author Message
Manager
Joined: 05 Feb 2012
Posts: 70
Followers: 0

Kudos [?]: 23 [1] , given: 2

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

27 Feb 2012, 18:39
1
KUDOS
Admissions is definitely not an exact science. I know a 550 GMAT 3.5 GPA in sociology with 1 year WE get into Stanford with a full ride!!! Also know a 2.3 GPA in EE with 610 GMAT get into Darden & Tuck with full ride (offered CGSM at Tuck & other scholarship at Darden). And as we've seen on this board great candidates with gpa & GMAT get dinged regularly. Essentially you have to put your absolute best application together and also have your app read by the right person on the ad com.

Imperfect system to say the least but what system is perfect? Going into the application it would be good to know this to properly set expectations. I think schools and even CGSM sells the idea that if you have good numbers, leadership, and WE you can get in and get $$which can be true but not always. Read between the lines and we will see that most things we think we know can and will be challenged. Posted from my mobile device Manager Joined: 02 Mar 2011 Posts: 129 Location: United States (TX) Concentration: Entrepreneurship, Strategy Schools: UCLA (Anderson) - Class of 2014 WE: Sales (Pharmaceuticals and Biotech) Followers: 0 Kudos [?]: 47 [0], given: 10 Re: Calling All Fall 2012 Consortium Applicants! [#permalink] ### Show Tags 27 Feb 2012, 19:53 Qwill wrote: Admissions is definitely not an exact science. I know a 550 GMAT 3.5 GPA in sociology with 1 year WE get into Stanford with a full ride!!! Also know a 2.3 GPA in EE with 610 GMAT get into Darden & Tuck with full ride (offered CGSM at Tuck & other scholarship at Darden). And as we've seen on this board great candidates with gpa & GMAT get dinged regularly. Essentially you have to put your absolute best application together and also have your app read by the right person on the ad com. Imperfect system to say the least but what system is perfect? Going into the application it would be good to know this to properly set expectations. I think schools and even CGSM sells the idea that if you have good numbers, leadership, and WE you can get in and get$$ which can be true but not always.

Read between the lines and we will see that most things we think we know can and will be challenged.

Posted from my mobile device

Is this Phil Knight's daughter and a dude whose daddy owns oil wells in Africa?

Posted from my mobile device
Intern
Joined: 06 Jan 2012
Posts: 9
Followers: 0

Kudos [?]: 5 [0], given: 1

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 01:03
Qwill wrote:
Admissions is definitely not an exact science. I know a 550 GMAT 3.5 GPA in sociology with 1 year WE get into Stanford with a full ride!!! Also know a 2.3 GPA in EE with 610 GMAT get into Darden & Tuck with full ride (offered CGSM at Tuck & other scholarship at Darden). And as we've seen on this board great candidates with gpa & GMAT get dinged regularly. Essentially you have to put your absolute best application together and also have your app read by the right person on the ad com.

Imperfect system to say the least but what system is perfect? Going into the application it would be good to know this to properly set expectations. I think schools and even CGSM sells the idea that if you have good numbers, leadership, and WE you can get in and get  which can be true but not always.

Read between the lines and we will see that most things we think we know can and will be challenged.

Posted from my mobile device

But as in most things it's who you know isn't it? As much as I hate the system I'm not naive or dumb enough to not know that obviously knowing someone and forging some type of positive relationship with the person or persons that makes these type of critical admission/scholarship decisions will undoubtedly make a world of difference. It's one of the reasons I'm holding off on applying. I plan on doing just that type of targeting to my #1 and #2 schools. It's something I didn't do and would prefer to not go in "blind" so to speak. At least for my top 2 choices.
Manager
Joined: 05 Feb 2012
Posts: 70
Followers: 0

Kudos [?]: 23 [0], given: 2

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 07:05
Nope, as far as I can tell they are just your everyday applicant. They both made no special connections with ad com, ad deans etc, not saying those things don't help but that there is no true exact science behind it, and no full proof plan. They didn't work with any notable F500 or save the world in their downtime. I'm just praying that the right set of circumstances befall me to be in the same situation as they are/were.

I talked to an admissions member I know at Darden after I read that someone on this forum didn't get in with a 770 & 3.7gpa and his first response was "that kid's probably going to Harvard so why would we accept him then he rejects us" that was an eye opener for me. So you turn down an overqualified candidate just like a job would, because they may not be happy/right/fit in with your program kind of makes sense but goes against everything we strive for as applicants. Again a point of view that would've been good to know prior to applying, it would save a lot headache & heart ache when stressing over every 10 points on the GMAT or sentence structure on an essay.

Posted from my mobile device
Manager
Joined: 16 Feb 2012
Posts: 65
Concentration: Nonprofit, Organizational Behavior
GPA: 3.45
WE: Marketing (Non-Profit and Government)
Followers: 0

Kudos [?]: 18 [0], given: 0

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 07:43
for those of you who have been waitlisted by Yale SOM, what are your next steps? I read through the FAQ they sent and it left me a bit confused, it sounded a bit like "if you don't get a promotion or retake the gmat don't bother contacting us"... thoughts?
Manager
Joined: 16 Feb 2012
Posts: 65
Concentration: Nonprofit, Organizational Behavior
GPA: 3.45
WE: Marketing (Non-Profit and Government)
Followers: 0

Kudos [?]: 18 [0], given: 0

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 07:54
Has there been any Haas activity recently? My application is still showing as "under review" .... at this point i'm assuming a ding.
Intern
Joined: 16 Feb 2012
Posts: 25
Schools: Dartmouth (Tuck) - Class of 2014
Followers: 0

Kudos [?]: 8 [0], given: 4

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 08:04
Qwill wrote:
I talked to an admissions member I know at Darden after I read that someone on this forum didn't get in with a 770 & 3.7gpa and his first response was "that kid's probably going to Harvard so why would we accept him then he rejects us" that was an eye opener for me. So you turn down an overqualified candidate just like a job would, because they may not be happy/right/fit in with your program kind of makes sense but goes against everything we strive for as applicants.

Call me naive, but I would imagine that for an "overqualified" applicant it would really come down to how well you can articulate your desire to be at the school. Any business school that encounters an applicant with those stats would be crazy not to at least give them a look... provided that they've shown a desire to be at that school. What if you really like a certain professor at the school, or you are enticed by a specific program and how well they place at your dream company, or you're tied to the location of that school in some way, etc etc? That stuff would hopefully come out in the essays/interview/your interaction with the school.

I don't even think the bar is *that* high to show your interest in a school and how well it matches with your career aspirations, especially for a smaller school that cares more about "fit" (like Darden seems to do). If you live outside of VA are and took the time/money to take a self-initiated trip, I would guess that would be significant. Or even attended a few Darden events in your area, or reached out proactively (read: not right before the app was due) to an alum... something that shows that you're not just throwing your name in the hat.

Anyway, I guess what I'm saying is: I think one of the big reasons that so many schools speak to fit and self-awareness on the MBA trail is because a lot of us applicants are not as self-aware as we might think, and a good chunk of us might need to show a commitment to schools that might not look like they make sense at face value. The adcoms are pretty good at determining which applicants put a full effort to their app and which ones come off in their interviews as genuine, even if we think we're pulling it off.

Just my .02.

Last edited by a82 on 28 Feb 2012, 08:51, edited 2 times in total.
Intern
Joined: 16 Feb 2012
Posts: 25
Schools: Dartmouth (Tuck) - Class of 2014
Followers: 0

Kudos [?]: 8 [0], given: 4

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 08:25
kheti wrote:
Has there been any Haas activity recently? My application is still showing as "under review" .... at this point i'm assuming a ding.

I've heard that Haas takes longer than most schools do. Haas R2 applicants (12/1 submit deadline) are just receiving their admit decisions now, and a few R2 folks on the Berkeley thread were getting interview invites into February.

My guess is that R2 Consortium applicants are tied somewhat to Haas's R3 schedule (1/18 submit deadline), which might be good news since I haven't read about any R3 Haas folks getting interview invites yet on the other thread.

It was also mentioned on this thread a while back that Haas supposedly has to manually transcribe our Consortium applications into their systems.. which sounds like it could take awhile. Plus, when you factor in the lag between our Consortium submit date and the time they take to make sure our apps are completed before forwarding them to the schools, etc etc

This is what I keep telling myself, anyway. lol.

All that said, I have no idea how their timelines impact the Consortium "Draft Day".
Intern
Joined: 12 Dec 2011
Posts: 16
Followers: 0

Kudos [?]: 5 [0], given: 0

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 11:59
a82 wrote:
kheti wrote:
Has there been any Haas activity recently? My application is still showing as "under review" .... at this point i'm assuming a ding.

I've heard that Haas takes longer than most schools do. Haas R2 applicants (12/1 submit deadline) are just receiving their admit decisions now, and a few R2 folks on the Berkeley thread were getting interview invites into February.

My guess is that R2 Consortium applicants are tied somewhat to Haas's R3 schedule (1/18 submit deadline), which might be good news since I haven't read about any R3 Haas folks getting interview invites yet on the other thread.

It was also mentioned on this thread a while back that Haas supposedly has to manually transcribe our Consortium applications into their systems.. which sounds like it could take awhile. Plus, when you factor in the lag between our Consortium submit date and the time they take to make sure our apps are completed before forwarding them to the schools, etc etc

This is what I keep telling myself, anyway. lol.

All that said, I have no idea how their timelines impact the Consortium "Draft Day".

I get the sense that even if there is a bit of a Consortium R2 Haas lag, that they've tried the best they could to lump in Consortium folks into R2 and not R3. My understanding is that all Consortium decisions go out March 1st (with notifications starting earlier). There might be some lags in this, but I think they'll obviously have to have all their admits and picks before the mid-March draft day.
Senior Manager
Joined: 29 Apr 2011
Posts: 311
Location: United States
Schools: Dartmouth (Tuck) - Class of 2014
WE: Corporate Finance (Real Estate)
Followers: 2

Kudos [?]: 45 [0], given: 1

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 12:01
cheetarah1980 wrote:
mooze wrote:
Just thought I would share a complete status on my app cycle,..in summary, NOT LOOKING GOOD! Breakdown is by Consortium ranking (R2).

1. Tuck - Self initiated interview
2. Haas - Heard nothing (assuming a ding if i havent heard by now)
3. Darden - Was contacted last Wednesday (2/22) by the lady in charge of Consortium apps, she asked me to fill out and send in a Va residency form. I did so the following Thursday (2/23). Besides that, nothing.
4. Ross - Invited to interview in the first wave, interviewed on Jan/22nd.
5. Yale - Ding w/ out interview.

Non-Consortium

Wharton - Ding w/ out interview (this was a far reach for me, so not that disappointed)

So right now its looking like a good chance Ross may be my only interview. In which case my chances of going to B-school would be 50/50. I was previously hopeful about Tuck,..but the fact that I was dinged w/out interview by so many schools of similar competitiveness has battered my confidence in a Tuck acceptance. The fact that all the marbles may be in the Ross bag has me so nervous.

Also, my stats for anyone curious,...3.1 gpa 680 Gmat....so not very good stats but I thought I had good story to tell and I've been told that I'm an exceptional writer and I felt my essays were very good.

It looks like i'll be sweating it to the very end. So thats my breakdown,..good luck everyone.

I know that Wharton is a reach for you and you're trying to be realistic about your chances. However, it's not over til it's over. Wharton DOES send invites on the last day. You may be surprised to find you have one tomorrow. Don't claim the ding before it's donged.

Was just officially DINGED at Wharton,..so, there it is.

I'm already lining up my resources for next year's cycle in the event I don't get into school this year,..but I pray Ross pulls through for me, otherwise it will be a long summer.

6 apps and so far only 1 interview to show for it. But I only need one.
Joined: 26 Mar 2007
Posts: 486
GMAT 1: 680 Q44 V38
Followers: 2

Kudos [?]: 54 [0], given: 123

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 12:07
mooze wrote:
cheetarah1980 wrote:
mooze wrote:
Just thought I would share a complete status on my app cycle,..in summary, NOT LOOKING GOOD! Breakdown is by Consortium ranking (R2).

1. Tuck - Self initiated interview
2. Haas - Heard nothing (assuming a ding if i havent heard by now)
3. Darden - Was contacted last Wednesday (2/22) by the lady in charge of Consortium apps, she asked me to fill out and send in a Va residency form. I did so the following Thursday (2/23). Besides that, nothing.
4. Ross - Invited to interview in the first wave, interviewed on Jan/22nd.
5. Yale - Ding w/ out interview.

Non-Consortium

Wharton - Ding w/ out interview (this was a far reach for me, so not that disappointed)

So right now its looking like a good chance Ross may be my only interview. In which case my chances of going to B-school would be 50/50. I was previously hopeful about Tuck,..but the fact that I was dinged w/out interview by so many schools of similar competitiveness has battered my confidence in a Tuck acceptance. The fact that all the marbles may be in the Ross bag has me so nervous.

Also, my stats for anyone curious,...3.1 gpa 680 Gmat....so not very good stats but I thought I had good story to tell and I've been told that I'm an exceptional writer and I felt my essays were very good.

It looks like i'll be sweating it to the very end. So thats my breakdown,..good luck everyone.

I know that Wharton is a reach for you and you're trying to be realistic about your chances. However, it's not over til it's over. Wharton DOES send invites on the last day. You may be surprised to find you have one tomorrow. Don't claim the ding before it's donged.

Was just officially DINGED at Wharton,..so, there it is.

I'm already lining up my resources for next year's cycle in the event I don't get into school this year,..but I pray Ross pulls through for me, otherwise it will be a long summer.

6 apps and so far only 1 interview to show for it. But I only need one.

You also still have Tuck, man.

It ain't over until the fat lady sings
Senior Manager
Joined: 29 Apr 2011
Posts: 311
Location: United States
Schools: Dartmouth (Tuck) - Class of 2014
WE: Corporate Finance (Real Estate)
Followers: 2

Kudos [?]: 45 [1] , given: 1

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 12:46
1
KUDOS
gablaze23 wrote:
You also still have Tuck, man.

It ain't over until the fat lady sings

True true....Oddly, thinking about and preparing for a next year cycle (although far from neccesary at this point) is kinda comforting. In a way it lets me know that even if the worst comes to fruition for this cycle, in the greater scheme of things its not that bad. A lot of us forget that fact in all our angst. I probably forget it more than most,...I've been a nervous wreck since Jan. 5th.
Manager
Joined: 02 Mar 2011
Posts: 129
Location: United States (TX)
Concentration: Entrepreneurship, Strategy
Schools: UCLA (Anderson) - Class of 2014
WE: Sales (Pharmaceuticals and Biotech)
Followers: 0

Kudos [?]: 47 [0], given: 10

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 12:54
I just called Haas.... again (I pray they don't recognize my voice at this point!) the woman I spoke with did say that Rd2 consortium did align more so with the general population's Rd2, and she believed MOST of the interview invitations for have gone out already at this point . Bummer, I spent SOOO much freggin effort on that Berkeley app that I'm gonna be bitter if I don't even get an interview. Hopefully there I still a ray of hope. I've always heard those border school (ranked 5-8 minus Kellogg) seemingly get caught up with stats more than the top 4. There my not be a shred of truth in that and may just be the jilted lover feeling talking, but at least that would give me something else to whine about.

F***ing GMAT

Posted from my mobile device

Posted from my mobile device
Manager
Joined: 27 Jul 2011
Posts: 192
Location: United States (CA)
GMAT 1: 730 Q44 V46
GMAT 2: 760 Q50 V44
GPA: 3.49
Followers: 3

Kudos [?]: 54 [0], given: 85

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 12:56
Just had my heart skip a beat when I looked in my inbox...

Email from Tuck:

Quote:
Dear, MyName
Greetings from Hanover! Thank you for applying to the Tuck School of the Business at Dartmouth College. I just wanted confirm that we have officially received your application and supporting materials from The Consortium for Graduate Study in Management. Your application is complete and is currently being reviewed by the Tuck Admission Committee as part of our January admission round. January round admission decisions will be released on March 16th 2012. Thanks again for your interest in Tuck and please feel to contact me if you should have any questions.
Best Regards,
Geoff Ringwald

Others get this, too? (just noticed - "Tuck School of the Business" oops )
_________________
Intern
Joined: 16 Feb 2012
Posts: 25
Schools: Dartmouth (Tuck) - Class of 2014
Followers: 0

Kudos [?]: 8 [0], given: 4

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 13:00
I just called Haas.... again (I pray they don't recognize my voice at this point!) the woman I spoke with did say that Rd2 consortium did align more so with the general population's Rd2, and she believed MOST of the interview invitations for have gone out already at this point . Bummer, I spent SOOO much freggin effort on that Berkeley app that I'm gonna be bitter if I don't even get an interview. Hopefully there I still a ray of hope. I've always heard those border school (ranked 5-8 minus Kellogg) seemingly get caught up with stats more than the top 4. There my not be a shred of truth in that and may just be the jilted lover feeling talking, but at least that would give me something else to whine about.

F***ing GMAT

*sigh* ah well, so much for the false hope. Good luck everyone.
Intern
Joined: 10 Jan 2012
Posts: 32
GMAT 1: 700 Q43 V44
GPA: 3.59
Followers: 0

Kudos [?]: 9 [0], given: 3

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 13:00
Any R2 applicants still waiting/hoping for a UCLA interview invite? Or should I start drinking now?
Manager
Joined: 05 Feb 2012
Posts: 70
Followers: 0

Kudos [?]: 23 [2] , given: 2

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 13:03
2
KUDOS
Faro,

I got that email from tuck, when I saw the subject line I almost pulled a "half baked" and quit my job and told everyone f-you, f-you, f-you, you're cool I'm out. good thing I read the email first, once my heart came back online, i could only laugh at how quickly my mind wandered to what that admit would mean, then went back to work with a smile on my face, thankful I have a great job, company, boss etc.

Posted from my mobile device
Intern
Joined: 28 Feb 2012
Posts: 1
GMAT 1: Q V
Followers: 0

Kudos [?]: 0 [0], given: 0

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 13:22
New to GMAT club. Consortium applicant. I got the same e-mal from Tuck. I swore I was in. The subject line is very decieveing. When is Tucks admitted students weekend? Does anyone know?
Manager
Joined: 23 Jan 2012
Posts: 97
Location: United States
Concentration: Operations, General Management
WE: Corporate Finance (Transportation)
Followers: 0

Kudos [?]: 23 [0], given: 7

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 13:32
My heart skipped a beat when I saw that Tuck email. That email was completely unnecessary.
Manager
Joined: 16 Feb 2012
Posts: 65
Concentration: Nonprofit, Organizational Behavior
GPA: 3.45
WE: Marketing (Non-Profit and Government)
Followers: 0

Kudos [?]: 18 [0], given: 0

Re: Calling All Fall 2012 Consortium Applicants! [#permalink]

### Show Tags

28 Feb 2012, 13:37
I just called Haas.... again (I pray they don't recognize my voice at this point!) the woman I spoke with did say that Rd2 consortium did align more so with the general population's Rd2, and she believed MOST of the interview invitations for have gone out already at this point . Bummer, I spent SOOO much freggin effort on that Berkeley app that I'm gonna be bitter if I don't even get an interview. Hopefully there I still a ray of hope. I've always heard those border school (ranked 5-8 minus Kellogg) seemingly get caught up with stats more than the top 4. There my not be a shred of truth in that and may just be the jilted lover feeling talking, but at least that would give me something else to whine about.

F***ing GMAT

Posted from my mobile device

Posted from my mobile device

I'm with you. My quant score was way lower than they like to see, and i knew it would be an issue but prayed that the fact i have a 3.5 and 30+ credits in finance and accounting would make up for it. guess not
Re: Calling All Fall 2012 Consortium Applicants!   [#permalink] 28 Feb 2012, 13:37

Go to page   Previous    1  ...  69   70   71   72   73  ...  118    Next  [ 2346 posts ]

Similar topics Replies Last post
Similar
Topics:
221 Calling All 2016 Consortium Applicants!!! 1281 14 Aug 2015, 05:05
540 Calling All 2015 Consortium Applicants Thread 1724 08 Aug 2014, 15:23
99 Calling All 2014 Consortium Applicants 559 24 May 2013, 08:15
288 Calling All Consortium 2013 Applicants 1109 26 Oct 2012, 01:06
62 Calling all Fall 2011 Consortium Applicants! 2638 08 Jun 2010, 00:12
Display posts from previous: Sort by


text:
# Computing by hand the optimal threshold value for a biomarker using the Youden Index

I have an empirical estimate of a ROC curve, that is, a plot of the sensitivity versus 1-specificity over all possible cut-off values of the marker. Based on an empirical ROC curve, I would like to determine the optimal cut-off point that represents a better trade-off between sensitivity and specificity. I have read that the Youden Index can be used in that purpose.

Here is an example:

oneMinusSpecificity <- c(1.00000000,
0.636363636,
0.436363636,
0.315151515,
0.163636364,
0.096969697,
0.072727273,
0.006060606,
0.000000000)
sensitivity <- c(1.00000000,
0.91566265,
0.77108434,
0.66265060,
0.39759036,
0.33734940,
0.28915663,
0.07228916,
0.00000000)

which results in the following ROC curve. The vertical line represents the Youden index = largest distance between "1 - specificity" and "sensitivity".

I find

> youden <- max(sensitivity - oneMinusSpecificity)
> youden
[1] 0.3474991

How can I calculate the optimal cut-off using this information?

• Please note that you are also in a gray zone of this site's scope; this seems like an R programming Q which might be asked on StackOverflow. Anyway, it would be easier to answer if you would make it reproducible, i.e. add information how you have calculated sensitivity and oneMinusSpecificity from the decision and raw biomarker level. – user88 May 13 '13 at 15:52


text:
A Functional Representation for Graph MatchingThis research is funded by NSFC-projects under the contracts No.61771350 and No.41820104006.

# A Functional Representation for Graph Matching††thanks: This research is funded by NSFC-projects under the contracts No.61771350 and No.41820104006.

Fu-Dong Wang, Gui-Song Xia, Nan Xue,
Yipeng Zhang, Marcello Pelillo,
LIESMARS-CAPTAIN, Wuhan University, Wuhan, China
School of Computer Science, Wuhan University, China

Computer Vision Lab., University of Venice, Italy
{fu-dong.wang, guisong.xia, xuenan, zhangyp}@whu.edu.cn,
pelillo@unive.it.
###### Abstract

Graph matching is an important and persistent problem in computer vision and pattern recognition for finding node-to-node correspondence between graph-structured data. However, as widely used, graph matching that incorporates pairwise constraints can be formulated as a quadratic assignment problem (QAP), which is NP-complete and results in intrinsic computational difficulties. In this paper, we present a functional representation for graph matching (FRGM) that aims to provide more geometric insights on the problem and reduce the space and time complexities of corresponding algorithms. To achieve these goals, we represent a graph endowed with edge attributes by a linear function space equipped with a functional such as inner product or metric, that has an explicit geometric meaning. Consequently, the correspondence between graphs can be represented as a linear representation map of that functional. Specifically, we reformulate the linear functional representation map as a new parameterization for Euclidean graph matching, which is associative with geometric parameters for graphs under rigid or nonrigid deformations. This allows us to estimate the correspondence and geometric deformations simultaneously. The use of the representation of edge attributes rather than the affinity matrix enables us to reduce the space complexity by two orders of magnitudes. Furthermore, we propose an efficient optimization strategy with low time complexity to optimize the objective function. The experimental results on both synthetic and real-world datasets demonstrate that the proposed FRGM can achieve state-of-the-art performance.

## 1 Introduction

Graph matching (GM) is widely used to find node-to-node correspondence [1, 2] between graph-structured data in many computer vision and pattern recognition tasks, such as shape matching and retrieval [3, 4], object categorization [5], action recognition [6], and structure from motion [7], to name a few. In these applications, real-world data are generally represented as abstract graphs equipped with node attributes (e.g., SIFT descriptor, shape context) and edge attributes (e.g., relationships between nodes). In this way, many GM methods have been proposed based on the assumption that nodes or edges with more similar attributes are more likely to be matched. Generally, GM methods construct objective functions w.r.t. the varying correspondence to measure similarities (or dissimilarities) between nodes and edges. Then, they maximize (or minimize) the objective functions to pursue an optimal correspondence that achieves maximal (or minimal) total similarities (or dissimilarities) between two graphs. In the literature, an objective function is generally composed of unary [3], pairwise [8, 9] or higher-order [10, 11] potentials. In practice, matching graphs using only unary potential (node attributes) might lead to undesirable results due to the insufficient discriminability of node attributes. Therefore, pairwise or higher-order potentials are often integrated to better preserve the structural alignments between graphs.

Although the past decades have witnessed remarkable progresses in GM [1], there are still many challenges with respect to both computational difficulty and formulation expression. Specifically, as widely used, GM that incorporates pairwise constraints can be formulated as a quadratic assignment problem (QAP) [12], among which Lawler’s QAP [13] and Koopmans-Beckmann’s QAP [14] are two common formulations. However, due to the NP-complete [15] nature of QAP, only approximate solutions are available in polynomial time. In practice, solving GM problems with pairwise constraints often encounters intrinsic difficulties due to the high computational complexity in space or time. For GM methods that apply Lawler’s QAP, the affinity matrix results in high space complexity w.r.t. the graph sizes . For GM methods that aim to solve the objective functions with discrete binary solutions through a gradually convex-concave continuous optimization strategy, the verbose iterations result in high time complexity. Restricted by these limitations, only graphs with dozens of nodes can be handled by these methods in practice.

In addition to the computational difficulties, how to formulate the GM model for real applications is also important. Representing real-world data in the conventional graph model can provide some generalities for the general GM methods mentioned above. However, their formulations can neither reflect the geometric nature of real-world data nor handle graphs with geometric deformations (rigid or nonrigid). For example, when the edge attributes of graphs are computed as distances [16, 17, 18] on some explicit or implicit spaces that contain the real-world data, the formulations of the original GM methods that define objective functions in the form of Lawler’s or Koompmans-Beckmann’s QAP ignore the geometric properties behind these data. They can only achieve generality and ignore the geometric nature of real-world data. For graphs with rigid or nonrigid geometric deformations [16], the original GM methods cannot compatibly handle the two tasks that estimate both correspondence and deformation parameters because they can hardly provide the correspondence a geometric interpretation that is naturally contained in the deformation parameters.

Facing these issues, this paper introduces a new functional representation for graph matching (FRGM). The main idea is to represent the graphs and the node-to-node correspondence in linear functional representations for both general and Euclidean GM models. Specifically, for general GM, as shown in Fig. 1, given two undirected graphs, we can identically represent the node sets as linear function spaces, on which some specified functionals (e.g., inner product or metric) can be compatibly constructed to represent the edge attributes. Then, between the two function spaces, a functional induced by the push-forward operation is represented by a linear representation map , which is exactly the correspondence between graphs. With these concepts, our general GM algorithm is proposed by minimizing the objective function w.r.t. that measures the difference of graph attributes between graph and its transformed graph . Namely, we want an optimal functional in the sense of preserving the inner product or metric. For the Euclidean GM in which the graphs are embedded in Euclidean space , the functional that plays the role of correspondence between graphs can be directly deduced on the background space . Due to the natural linearity of , can also be represented by a linear representation map , which is not only a parameterization for GM but also associative with geometric parameters for graphs under geometric deformations. A preliminary version of this work was presented in [19].

FRGM only needs to compute and store the edge attributes of graphs; thus its space complexity is (with ). To reduce the time complexity, we first propose an optimization algorithm with time complexity based on the Frank-Wolfe method. Then, by taking advantage of the specified property of the relaxed feasible field, we improve the Frank-Wolfe method by an approximation that has a lower time complexity of .

The contributions of this paper can be distinguished in the following aspects:

• We introduce a new functional representation perspective that can bridge the gap between the formulation of general GM and the geometric nature behind the real-world data. This guides us in constructing more efficient objective functions and algorithms for general GM problem.

• For graphs embedded in Euclidean space, we extend the linear functional representation map as a new geometric parameterization that achieves compatibility with the geometric parameters of graphs. This helps to globally handle graphs with or without geometric deformations.

• We propose GM algorithms with low space complexity and time complexity by avoiding the use of an affinity matrix and by improving the optimization strategy. The proposed algorithms outperform the state-of-the-art methods in terms of both efficiency and accuracy.

The remainder of this paper is organized as follows. Sec. 2 presents the mathematical formulation and related work of GM. In Sec. 3 we demonstrate the functional representation for GM in general settings and the resulting algorithm. In Sec. 4 and Sec. 5, we discuss FRGM for matching graphs in Euclidean space with and without geometric deformations, respectively. In Sec. 6, we present a numerical analysis of our optimization strategy. Finally, we report the experimental results and analysis in Sec. 7 and conclude this paper in Sec. 8.

## 2 Background and Related Work

This section first introduces the preliminaries and basic notations of GM and then it discusses some related works on GM.

### 2.1 Definition of GM Problem

An undirected graph of size is defined by a discrete set of nodes and a set of undirected edges such that . Generally, the edge of graph is written as a symmetric edge indicator matrix (also denoted as) , where if there is an edge between and , and otherwise. An important generalization is the weighted graph defined by the association of non-negative real values to graph edges, and is called adjacency weight matrix. We assume graphs with no self-loop in this paper, i.e., .

In many real applications, graph is associated with node and edge attributes expressed as scalars or vectors. For an attribute graph , we denote as the node attribute of and as the edge attribute of . Typically, an edge attribute matrix will be calculated by some user-specified functions such as or .

Given two graphs of size and () respectively, the GM problem is to find an optimal node-to-node correspondence , where when the nodes and are matched and otherwise. It is clear that any possible correspondence equals a (partial) permutation matrix when GM imposes the one-to-(at most)-one constraints. Therefore, the feasible field of can be defined as:

 P≜{P∈{0,1}m×n;P1n=1m,PT1m≤1n}, (1)

where is a unit vector. When , is orthogonal: , where is a unit matrix.

To find the optimal correspondence, GM methods that incorporate pairwise constraints generally minimize or maximize their objective functions w.r.t. upon the feasible field . There are two main typical objective functions: Lawler’s QAP [13] and Koopmans-Beckmann’s QAP [14].

The main idea behind Lawler’s QAP [13, 8, 20, 9, 16] is to maximize the sum of the node and edge similarities:

 maxP∈PPTvKPv=∑ijPijKij;ij+∑(i1,i2)(j1,j2)Piij1Ki1j1;i2j2Pi2j2, (2)

where is the columnwise vectorized replica of . The diagonal element measures the node affinity calculated with node attributes as , and measures the edge affinity calculated with edge attributes as . is called the affinity matrix of and .

Koopmans-Beckmann’s QAP [14, 21] formulates GM as

 maxP∈P−tr(UTP)+λtr(E1PE2PT), (3)

where measures the dissimilarity between node and , and are the adjacency weight matrices of and . is a weight between the unary and pairwise terms. This formulation differs from Eq. (2) mainly in the pairwise termï¼ which measures the edge compatibility as the linear similarity of adjacency matrices and . In fact, Eq. (3) can be regarded as a special case of Lawler’s QAP (Eq. (2)) if , where denotes the Kronecker product. With this formulation, the space complexity of GM is and much lower than that of Eq. (2).

The Eq. (3) has another approximation, which aims to minimize the node and edge dissimilarity between two graphs:

 minP∈P⟨P,U⟩F+λ2||E1−PE2PT||2F, (4)

where is the Frobenius dot-product defined as and is the Frobenius matrix norm defined as . The conversion from Eq. (4) to Eq. (3) holds equally under the fact that any is an orthogonal matrix.

Due to the NP-complete nature of the above formulations, GM methods generally approximate the discrete feasible field by a continuous relaxation , which is known as the doubly stochastic relaxation. Then the objective functions can be approximately solved by applying constrained optimization methods and employing a post-discretization step such the Hungarian algorithm [22] to obtain a discrete binary solution.

### 2.2 Related Work

Over the past decades, the GM problem of finding node-to-node correspondence between graphs has been extensively studied [2, 1]. Earlier works (exact GM) [23, 24] tended to regard GM as (sub)graph isomorphism. However, this assumption is too strict and leads to less flexibility for real applications. Therefore, later works on GM (inexact/error-tolerant GM) [18, 16, 20, 9] focused more on finding inexact matching between weighted graphs via optimizing more flexible objective functions.

Among the inexact GM methods, some of them aim to reduce the considerable space complexity caused by the affinity matrix in Eq. (2). A typical work is the factorized graph matching (FGM) [16], which factorized as a Kronecker product of several smaller matrices. An efficient sampling heuristic was proposed in [25] to avoid storing the whole at once. Some works [21, 26] constructed objective functions similar to Eq. (4) or Eq. (3) to avoid using matrix . Our work use the representation of edge attributes rather than .

Since exactly solving the objective functions upon discrete feasible field is NP-complete, most GM methods relax for approximation purpose in several ways. The first typical relaxation is spectral relaxation, as proposed in [8, 27], by forcing ; then, the solution is computed as the leading eigenvector of . The second relaxation [21] is to consider as a subset of an orthogonal matrices set such that , which is the basis of converting Eq. (4) into Eq. (3). Semidefinite-programming (SDP) was also applied to approximately solve the GM problem in [28, 29] by introducing a new variable under the convex semidefinite constraint . Then, is approximately recovered by .

The most widely used relaxation approach is the doubly stochastic relaxation , which is the convex hull of . Since is a convex set defined in a linear form, it allows the GM objectives functions to be solved by more flexible convex or nonconvex optimization algorithms. To find more global optimal solutions with a binary property, the algorithms proposed in [21, 16, 30, 31] constructed objective functions in both convex and concave relaxations controlled by a continuation parameter, and then they developed a path-following-based strategy for optimization. These approaches are generally time consuming, particularly for matching graphs with more than dozens of nodes. The graduated assignment method [32] iteratively solved a series of first-order approximations of the objective function. Its improvement [33] provided more convergence analysis. The decomposition-based work in [34] developed its optimization technique by referring to dual decomposition. Additionally, another method in [18] decomposed the matching constraints and then used an optimization strategy based on the alternating direction method of multipliers. To ensure binary solutions, some methods such as the integer-projected fixed point algorithm [20] and iterative discrete gradient assignment [11], have been proposed by searching in the discrete feasible domain. We also adopt the doubly stochastic relaxation, and we construct an objective function that can be solved with a nearly binary solution, which helps to reduce the effect of the post-discretization step.

In addition to approximating the objective functions, some works also intended to provide more interpretations of the GM problem. The probability-based works [25, 35] solved the GM problem from a maximum likelihood estimation perspective. Some learning-based works [36, 37] went further to explore how to improve the affinity matrix by considering rotations and scales of real data. A pioneering work [38] presented an end-to-end deep learning framework for GM. A random walk view [9] was introduced by simulating random walks with reweighting jumps. A max-pooling-based strategy was proposed in [39] to address the presence of outliers. Compared to these these works, the proposed FRGM provides more geometric insights for GM with general settings by using a functional representation to interpret the geometric nature of real-world data, and it then matches graphs embedded in Euclidean space by providing a new parameterization view to handle graphs under geometric deformations.

## 3 Functional Representation for GM

This section presents the functional representation for general GM that incorporates pairwise constraints. In Sec. 3.1, we introduce the function space of a graph, on which functionals can be defined as the inner product or metric to compatibly represent the edge attributes. In Sec. 3.2, we discuss how to represent the correspondence between graphs as a linear functional representation map between function spaces. Finally, the correspondence is an optimal functional map obtained by the algorithm in Sec. 3.3.

### 3.1 Function Space on Graph

Given an undirected graph with edge attribute matrix , we aim to establish function space of , on which some geometric structures, such as inner product or metric can be defined. This is especially meaningful when graphs are embedded in explicit or hidden manifolds.

Let denote the function space of all real-valued functions on . Since is finite discrete, we can choose a finite set of basis functions to explicitly construct .

###### Definition 3.1.

The function space on graph can be defined as:

 F(V,R)≜{ϕa=∑iaiϕi,a≜(a1,...,am)T∈Rm}. (5)

For example, can be chosen as the indicator of :

 ϕi:V→R,ϕi(Vj)={1,j=i.0,j≠i. (6)

Considering the fact that the correspondence matrix is positive, i.e., , a typical subset of can be defined as follows, which is the convex hull of :

 C(V,R)≜{ϕa=∑iaiϕi;∑iai=1,a∈Rm+}. (7)

Once the function space is built, some trivial operations can be defined, e.g., inner product and metric . However, these definitions cannot express the edge attribute . Therefore, we aim to define some other operations to represent based on . An available approach is to define functionals on the product space . Moreover, the functionals should (1) be compatible with and (2) have geometric structures such as inner product or metric, as demonstrated in the following:

###### Definition 3.2.

A functional is compatible with if it satisfies .

Among all the compatible functionals, there are some specified ones that can be defined as the inner product or metric on the function space or its subset , as follows.

###### Definition 3.3.

The inner product on the function space can be defined in an explicit form: ,

 FV(ϕa,ϕb) ≜∑i1,i2ai1bi2FV(ϕi1,ϕi2)=∑i1,i2ai1bi2Ei1i2. (8)

For the given edge attribute matrix that is symmetric, satisfies the first two inner product axioms: symmetry and linearity. To satisfy the third axiom, positive-definiteness, we need more knowledge about , e.g., is positive-definite. However, if the positive-definiteness is too strong, we can relax it to a weaker condition.

###### Proposition 1.

Assume that satisfies iff . Then, the functional in Eq. (8) satisfies all three axioms on by replacing with with small enough. Here, is a pointwise product.

This proposition holds because when is sufficiently small, all the eigenvalues of matrix will be positive. In particular, when is computed as a metric (distance) matrix on an explicit or hidden manifold, it satisfies that and is positive-definite. Moreover, can be used to adjust the eigenspace of . Fig. 2 illustrates an empirical study on thousands of ’s extracted from both realistic and synthetic datasets used in Sec. 7. The edge attribute of each graph is computed in a metric form (either Euclidean distance or geodesic distance) and then normalized to divided by the maximum element. We can see that

• All the eigenvalues of are positive.

• The ratio between the minimum and maximum eigenvalues has a similar tendency when varies from to .

It shows that will become indistinguishable if is too small or unbalanced if is too large. We can choose a suitable to adjust the eigenspace of to achieve better matching performance.

The inner product can induce a metric by definition . Moreover, we can also define another metric on the subset based on itself.

###### Definition 3.4.

The metric on the convex hull can be defined in an implicit form: ,

 FV(ϕa,ϕb) =minπ∈P(a,b)πi1i2FV(ϕi1,ϕi2)=minπ∈P(a,b)πi1i2Ei1i2, (9)

where .

When is computed as a metric, satisfies all three distance axioms on , and it is a typical Wasserstein distance (or Sinkhorn distance) [40]. The definition in Eq. (9) is not differentiable w.r.t. ; one can use the entropy-regularized Wasserstein distance [40] to achieve differentiability.

With the function space equipped with inner product or metric, each graph is assigned with explicit geometric structures that are compatible with the edge attribute. Next, we demonstrate the idea of using the functional map representation to formulate the correspondence between graphs as a functional between two function spaces .

### 3.2 Functional Map Representation for GM

The matching between two graphs and can be viewed as a mapping from to , which may be nonlinear and complicated. Therefore, we use the push-forward operation to induce a functional rather than to equally represent the matching between graphs.

Assume that is an injective mapping; then, is bijective and invertible. Without ambiguity, we can assume that is bijective. Each induces a natural transformation via the push-forward operation, which is widely used in functional analysis [41] and real applications [42][43]:

###### Definition 3.5.

The functional induced from is defined as: , the image of is .

###### Proposition 2.

The original can be recovered from .

For each point , it can be associated with an indicator function as Eq. (6). To recover the image from , we utilize the function , which satisfies

 ψ(V)≜ϕ∘T−1(V)={1,T−1(V)=V(1)i,0,T−1(V)≠V(1)i. (10)

Since is bijective and invertible, a unique exists s.t. . Then, once we find , we have , and must equal the image of : . Thus, the functional can be used to equally represent .

###### Proposition 3.

is a linear mapping from function spaces to .

It holds because ,

 TF(α1f1+α2f2) =(α1f1+α2f2)∘T−1 =α1f1∘T−1+α2f2∘T−1 =α1TF(f1)+α2TF(f2).

Although may be nonlinear and complicated, is linear and simple.

With function spaces and defined by basis functions and respectively, each basis function can be transformed into and represented in a linear form as . Whenever reaches an extreme point of the feasible field , it is a binary correspondence between graphs, and consequently, is transformed into (i.e., matches) a , where .

To find an optimal correspondence between two graphs with edge attributes and , we declare that the induced functional should be able to preserve the geometric structures defined on function spaces. Namely, should be the inner product or metric preserving. More precisely, for each pair , the functional value should be similar to the functional value of the transformed pair , which is calculated as

 FV2(TF(ϕi1),TF(ϕi2))=FV2(n∑j=1Pi1jψj,n∑j=1Pi2jψj). (11)

The functionals defined in Definition 3.3 or Definition 3.4 can be used to calculate it. Finally, to incorporate the pairwise constraints, we aim to minimize the total sum as follows:

 ∑(i1,i2)E1iii2[FV1(ϕi1,ϕi2)−FV2(TF(ϕi1),TF(ϕi2))]2 ≜ ∑(i1,i2)E1iii2[E1i1i2−F(P)i1i2]2≜||E1−F(P)||2F,E1, (12)

where is computed based on the edge attributes matrix . Note tha the affinity matrix with size is replaced here by the edge attributes matrix with size and with size .

### 3.3 FRGM-G: matching graphs with general settings

Here, we propose our FRGM-G algorithm for matching graphs with general settings, i.e. without knowledge on the geometrical structures of the graphs. To find an optimal correspondence, i.e., functional map mentioned above, we first minimize an objective function as

 Jori(P)=(1−α1)⟨P,U⟩F+α1||E1−F(P)||2F,E1, (13)

where balances the weights of the unary term and pairwise term. In general, is nonconvex and minimizing upon the feasible field results in a local minimum. The minimizer may be not binary, and the post-discretization of may reduce the matching accuracy. Therefore, we next construct another objective function to find a better solution based on the obtained .

According to the definition , each lies in the convex set , which is the convex hull of . Therefore, the transformed functions lies in the same function space spanned by , and the offset between and can be controlled. Moreover, since indeed preserves the pairwise geometric structure between two graphs, will lie closer to the correct matching . This means that, based on the metric defined on the function spaces, the distance make sense and will be smaller than . Therefore, we define the second objective function as:

 Jint(P) =(1−α2)⟨P,D⟩F+α2||F(P∗1)−F(P)||2F,E1, (14)

where is the distance between and computed by the metric functional defined on or . The minimizer can be viewed as a displacement interpolation: to minimize we obtain a solution that is an extreme point (thus, binary) of the feasible field ; to minimize , we obtain a solution that equals . Then, is an interpolation between and controlled by . Finally, we use the Hungarian method to discretize into being binary.

## 4 FRGM in Euclidean Space

In many computer vision applications, graphs are often embedded in explicit or implicit manifolds , e.g., Euclidean space and surface , where graphs with nodes are naturally associated with some specific geometric properties. For example, the node attributes can be computed as SIFT [44], shape context [3], HKS [45] and so on, and the edge attribute matrix can be computed as Euclidean distance on or geodesic distance on surface .

We can use the proposed method for general GM in Sec. 3 to match graphs in these cases. Furthermore, for graphs embedded in , we can construct another method for Euclidean GM based on the fact that the functional representation of between abstract function spaces can be deduced into the concrete Euclidean space with explicit geometric interpretations. Since each node can be represented as a vector , the expression naturally makes sense. Consequently, we can directly define the unknown transformation in a linear form:

 T:V1 →V2, (15) V(1)i↦T(V(1)i) =n∑j=1PijV(2)j. (16)

The transformed nodes can be rewritten in a matrix notation and . Now, is a linear representation map of the unknown transformation . With the constraint that , each node lies in the convex hull of . Once reaches a binary correspondence matrix, is transformed into , where .

For graphs embedded in Euclidean spaces, the edge attributes, such as edge length and edge orientation, are widely used. The edge attributes of the transformed graph can be computed as a function w.r.t. as:

• edge length computed as the Euclidean distance

 ||T(V(1)i1)−T(V(1)i2)||=||(PV2)i1−(PV2)i2||,
• edge orientation computed as the vector between nodes

 −−−−−−−−−−−−−−−→T(V(1)i1)−T(V(1)i2)=−−−−−−−−−−−−−−→(PV2)i1−(PV2)i2,

where is the Euclidean norm. We propose our algorithm for matching graphs in Euclidean space, i.e. FRGM-E, in the following sections.

### 4.1 Preserving edge-length

Given two graphs with visually similar structures, a general constraint is to preserve the edge length between the original edge and its corresponding edge . Thus, the pairwise potential of the first objective function can be defined as follows:

 Jnon(P) =∑(i1,i2)E1i1i2(||V(1)i1i2||−||T(V(1)i1i2)||)2 (17) =∑(i1,i2)E1i1i2(||V(1)i1i2||−||(PV2)i1i2||)2. (18)

We can add a unary term computed with node attributes to this pairwise term as follows:

 Jnon(P) =(1−λ1)⟨P,U⟩F+λ1∑(i1,i2)E1i1i2(||V(1)i1i2||−||(PV2)i1i2||)2. (19)

Due to the nonconvexity of , its solution often reaches a local minimum and is not binary, and the post-discretization procedure will result in low accuracy; see Fig. 3 (b) for illustration. Consequently, the transformed node is not exactly equal to a , and there is often an offset between and its correct match . Fig. 3 (a) shows this phenomenon, where each shifts from the correct match to some degree.

### 4.2 Reducing node offset

Benefiting from the property of the solution that preserves the edge length of , the offset vectors of adjacent transformed nodes in have similar directions and norms, as shown in Fig. 3 (a). To reduce the node offset from to the corresponding correct match denoted by

 −−−−−−−−−→(P∗1V2)iV(2)δi=V(2)δi−(P∗1V2)i,

we aim to minimize the sum of differences between adjacent offset vectors, i.e.,

 Jcon(P) =∑(i1,i2)Si1i2||((PV2)i1−(P∗1V2)i1)−((PV2)i1−(P∗1V2)i1)||2 =Tr((PV2−P∗1V2)TLS(PV2−P∗1V2)), (20)

where and is computed to indicate the adjacency relation of node pair . The undirected graph here will result in a symmetric ; therefore is positive-definite and is convex.

Compared to the algorithm proposed for general GM in Sec. 3.3, the distance matrix here can be computed with an explicit geometric interpretation: is the Euclidean distance between the transformed node and . As shown in Fig. 3 (c), is smaller than , where denotes the correct matching of . Therefore, the unary term can be added as a useful constraint during matching. Finally, is summarized as:

 Jcon(P) =(1−λ2)⟨P,D⟩F+λ2Tr((PV2−P∗1V2)TLS(PV2−P∗1V2)). (21)

In general, this objective function is solved by a (nearly) binary solution if is small. This significantly improves the matching accuracy. See Fig. 3 (d) as an example.

### 4.3 Explicit outlier-removal strategy

In practice, outliers generally occur in graphs and affect the matching accuracy. Based on the ability of the optimal representation map and that preserves the geometric structure between and the transformed graph or , we can propose an explicit outlier-removal strategy.

The transformed graph with nodes lies in the convex hull of . In some sense, the operation can be viewed as a domain adaptation [46] from the source domain to the target domain . The graph has a geometric structure similar to the original graph and lies in the same space of with a relatively small offset. Then, we can remove outliers adaptively using a ratio test technique. Given two point sets and , we compute the Euclidean distance of all the pairs . For each node , we find the closest node and remove all the nodes when for a given . If the number of remaining nodes is less than , nodes are selected from the removed ones that are closer to and added. See Fig. 4 as an example, where after several iterations most outliers are removed. More experimental results are reported in the experimental section.

## 5 FRGM with Geometric Deformation

For Euclidean GM, rigid or nonrigid geometric deformations may exist between graphs. In these cases, we need to estimate both the correspondence and deformation parameters. This section demonstrates that the FRGM can provide a new parameterization of transformation between graphs. Due to the associative law of matrix multiplication, this parameterization is associative with the deformation parameters. Theoretically, this allows us to estimate the correspondence and deformation parameters alternately.

### 5.1 Geometric deformation

Given two point sets with geometric transformation , the task to estimate both the correspondence and parameters of is generally formulated as minimizing the sum of residuals:

 minP∈P,τ∈χJ(P,τ)=∑i,jPij||V(1)i−τ(V(2)j)||2+Υ(τ), (22)

where is a regularization term of . On the one hand, most of the state-of-the-art registration algorithms such as [47, 48, 49] do not explicitly recover the correspondence as a binary solution. Rather, they estimate in a soft way as to give a probability interpretation: stands for the correspondence probability between and


text:
# existence of a connected set with given connected projections.

Suppose A and B are compact connected sets in the XY plane and XZ plane respectively in R^3. Suppose further that the the range of x-values taken by A and B are the same (i.e, projections of A and B onto the x-axis are the same closed interval). Is there always a connected set in R^3 whose projections onto XY and XZ planes are A and B respectively?

-

Let $\alpha,\beta:[0,1]\to[0,1]\times \mathbb R$ be two paths; $\alpha(t)=\left(\alpha_1(t),\alpha_2(t)\right)$ and $\beta(t)=\left(\beta_1(t),\beta_2(t)\right)$. Assume that $\alpha_1(0)=\beta_1(0)=0$, $\alpha_1(1)=\beta_1(1)=1$.

Claim. The points $a=\left(0,\alpha_2(0),\beta_2(0)\right)$ and $b=\left(1,\alpha_2(1),\beta_2(1)\right)$ lie in the same connected coponent of the set $\Sigma\subset \mathbb R^3$ formed by points of the following type $\left(\alpha_1(t),\alpha_2(t),\beta_2(\tau)\right)$ such that $\alpha_1(t)=\beta_1(\tau)$.

Proof. Note that for generic smooth choice of $\alpha$ and $\beta$ the set $\Sigma$ is a smooth 1-dimensional manifold which might be not connected, but it has only two boundary points in $a$ and $b$. Thus, in this case one can connect these points by a curve. The general case can be done by approximation. $\square$

The rest is easy: one can approximate $A$ and $B$ by path-connected sets $A'$ and $B'$ with the same property. Thus one can present $A'$ and $B'$ as a union of curves $\alpha$ and $\beta$ with the above property. Moreover we can assume that the ends of $\alpha$ and $\beta$ are fixed (i.e. $a$ and $b$ are fixed). For each pair $(\alpha,\beta)$, choose the connected component of $a$ in $\Sigma$ and take the union of all of them.

-
Nice answer!. Could you point me to a reference to the fact: "a connected set in the plane can be approximated by path connected set". –  arun s Mar 8 '10 at 7:53
A connected open set in the plane has to be path-connected (that is standard fact and it is easy to prove). So you may pass to $\epsilon$-neighborhood of your set (and take its closure if you want to keep it compact). –  Anton Petrunin Mar 8 '10 at 15:44

Edit: This answer is wrong. But, since Anton based his answer on this idea, I am leaving it up.

No. Let $A$, resp. $B$, be the graph $x=f(y)$, resp. $x=g(z)$, for some continuous functions $f$ and $g$. Pick numbers $0<d<b<a<c<1$, and arrange things so that $f(0)=g(0)=0$, $f(1)=g(1)=1$, and $f(y)$ grows from 0 to $a$, then decreases to $b$, then finally increases to 1, whereas $g(z)$ grows from $0$ to $c$, decreases to $d$, and increases to 1. (Here, $a$, $b$, $c$, $d$ are function values, i.e., values of $x$, not of the arguments $y$ or $z$.)

Now if $C$ projects to $A$ and $B$, respectively, it is not hard to see that $(0,0,0)\in C$ and $(1,1,1)\in C$. Trying to move $(x,y,z)$ continuously from the former to the latter, a contemplation of how $x$ must grow and shrink in order to maintain $x=f(y)$ and $x=g(z)$ leads to a contradiction. (Hard to put in words, but a pair of graphs reveals it I think.)

-
No, it is connected. –  Anton Petrunin Mar 7 '10 at 18:27
Rats. You're right. I had mislabeled one of my pictures. –  Harald Hanche-Olsen Mar 7 '10 at 19:07
It was nice mistake, I made my answer based on it :) –  Anton Petrunin Mar 7 '10 at 19:12
To the "edit": No, you can not make an example this way; it follows directly from my answer. (It also contains an answers to the original question, but you need some extra technical steps.) –  Anton Petrunin Mar 7 '10 at 20:09
Right; I see it now. I edited the “edit”. –  Harald Hanche-Olsen Mar 7 '10 at 22:54


text:
• •

### 多维极化的测度:新的方法及其应用

• 出版日期:2020-09-25 发布日期:2020-09-18

### Multidimensional Polarization: New Measurement and Its Application

Hong Xingjian Dong Jun

• Online:2020-09-25 Published:2020-09-18

Abstract: As the existing measurements of multidimensional polarization fail to reflect the correlation between dimensions, this paper introduces cosine similarity, and proposes a new multidimensional polarization measurement based on the relative deprivation theory. The method can also be decomposed statically and dynamically, and can analyze the contribution rate of each dimension and its change to multidimensional polarization. Using the data from China Family Panel Studies (CFPS), this paper empirically analyzes the multidimensional polarization between urban and rural households in China from four dimensions: income, properties, expenditure on transportation and communications, and educational level. The empirical results show that the long-term multidimensional polarization shows a significant downward trend, and the polarization effect of education, expenditure on transportation and communications, and income is the main reason, but the polarization effect of properties promotes multidimensional polarization.


text:
## Results (displaying all 8 matches)

Polynomial $p$ $e$ $f$ $c$ Galois group Slope content
x15 + 3x2 - 2x + 2 7 1 15 0 $C_{15}$ (as 15T1) $[\ ]^{15}$
x15 + 4116x6 - 2401x3 + 1075648 7 3 5 10 $C_{15}$ (as 15T1) $[\ ]_{3}^{5}$
x15 - 2401x3 + 67228 7 3 5 10 $C_{15}$ (as 15T1) $[\ ]_{3}^{5}$
x15 - 98x9 + 2401x3 - 268912 7 3 5 10 $C_{15}$ (as 15T1) $[\ ]_{3}^{5}$
x15 - 49x5 + 686 7 5 3 12 $F_5\times C_3$ (as 15T8) $[\ ]_{5}^{12}$
x15 - 7 7 15 1 14 $F_5\times C_3$ (as 15T8) $[\ ]_{15}^{4}$
x15 + 14 7 15 1 14 $F_5\times C_3$ (as 15T8) $[\ ]_{15}^{4}$
x15 - 28 7 15 1 14 $F_5\times C_3$ (as 15T8) $[\ ]_{15}^{4}$


text:
<meta http-equiv="refresh" content="1; url=/nojavascript/"> Median ( Read ) | Statistics | CK-12 Foundation
You are viewing an older version of this Concept. Go to the latest version.

# Median

%
Progress
Practice Median
Progress
%
Median - Probability and Statistics

#### Objective

Here you will investigate the calculation and use of the median value of a data set.

#### Concept

What is the median value of a data set? Why would you need to know how to find it if you already know how to find the mean? Is there really any difference? Can you think of a situation where the mean and median are exactly the same number?

In the lesson below we will discuss all of these concepts, and you should have no problem with answering these questions when we review them after example C.

#### Watch This

http://youtu.be/kZcuGPoqM9c ehow – Math Definitions: What is a Median Value?

#### Guidance

The median is defined as the value representing the “middle number” of a data set that has been ordered by increasing value, meaning that exactly  $\frac{1}{2}$ of the data is greater than the median, and $\frac{1}{2}$ is less. Finding the median value of a set is a very simple process, requiring very little or no actual calculation at all. Regardless, it can be an excellent representation of the central tendency of a set. The median is particularly useful when evaluating sets with multiple non-representative outliers, since the median is not sensitive to very large or very small values at the extremes of a data set.

To identify the median:

• First, organized your set in ascending numerical order and count the values:
• Second:
• If there are an odd number of values, the median is the middle number in the series.
• If there is an even number of values, the median is the arithmetic mean of the two middle numbers in the series.

Example A

Find the median of $z$ .

$z=\{1, 10, 3, 8, 5, 6, 7, 4, 9, 2, 13, 12, 15, 19 \}$

Solution: First, organize the numbers in ascending numerical order and count the values:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 19: total of 14 values

Since there is an even number of values (14 of them), the median is the arithmetic mean of the 7 th   and 8 th numbers in the series: $\frac{7+8}{2}=7.5$

$\therefore 7.5 \ \text{is the median of set} \ z$

Example B

Find the median of set $x$ .

$x=\left \{\frac{1}{8}, \frac{3}{4}, \frac{4}{5}, \frac{19}{21}, \frac{17}{20}, \frac{31}{42}, \frac{2}{3}, \frac{5}{8}, \frac{3}{8}, \right \}$

Solution: First, organize the values in ascending numerical order and count them:

$\frac{1}{8}, \frac{3}{8}, \frac{5}{8}, \frac{2}{3}, \frac{31}{42}, \frac{3}{4}, \frac{4}{5}, \frac{17}{20}, \frac{19}{21}$  : Total of 9 values

• Since there are an odd number of values (9 of them), the median is the 5 th value: $\frac{31}{42}$ .

$\therefore \ \frac{31}{42} \ \text{is the median of set} \ x$

Example C

Brian is looking for an entry-level job at a retail store, and is debating between two options. If he wants to apply for the highest paying job, which of the two employers described below should he choose? Why?

 Employer #1 Employer #2 Company’s mean salary: $48,000 Company’s mean salary:$42,000 Company’s median salary $22,000 Company’s median salary:$28,000

Solution: Since Brian is looking for an entry-level position, he would likely earn more income with Employer #2.

Recall that the mean salary is the average of all the salaries in the company, including any managers or owners on the payroll. Since those positions are undoubtedly higher paid, they would artificially raise the mean income well above that of most employees.

By contrast, the median income is probably closer to the salary of a typical salesman, since there would be many more salesmen than managers or owners.

Concept Problem Revisited

What is the median value of a set? Why would you need to know how to find it if you already know how to find the mean? Is there really any difference? Can you think of a situation where the mean and median are exactly the same number?

The median value is the middle number when the set is organized in ascending numerical order. Depending on the composition of the set, there can actually be quite a large difference between the mean and the median, the mean being much more influenced by outliers. In a normally distributed set, the mean, median, and mode are all the same.

#### Vocabulary

The median is the middle number in a set that has been organized in ascending numerical order.

Central tendency is a measure of the central or typical value in a set.

A normally distributed set has, among other characteristics, an equal mean, median, and mode.

#### Guided Practice

Identify the median of each set in Q’s 1 - 4:

1. .

$\{12, 17, 32, 63, 85, 12, 54, 23, 39 \}$

2.  .

$\begin{array}{c|c c c c c c c c c c c c c c c c c c c} 6 & 7 & 7 & 9 \\7&3&4&4&6&8&9 \\8&0&1&2&3&3&3&3&4&4&6&7&7\\9&0\end{array}$

3. .

$\{93, 91, 95, 92, 92, 93, 95, 94, 97, 93, 86, 92, 94, 89, 92, 91, 92, 93, 94, 100 \}$

4. .

$\{275, 281, 269, 280, 268, 278, 279, 274, 275, 281, 285, 285, 278, 269, \\~~~~~~~283, 263, 277, 276, 269, 281, 272, 275, 276 \}$

Solutions:

1. Put the values in numerical order first: 12, 12, 17, 23, 32, 39, 54, 63, 85. There are nine values, an odd count, so we just take the middle number. 32 is the median.

2. First, put the values in numerical order, remembering that, as a stem plot, this data is listed with the tens place to the left of the vertical, and each separate ones place to the right. That means our values are: 67, 67, 69, 73, 74, 74, 76, 78, 79, 80, 81, 82, 83, 83, 83, 83, 84, 84, 86, 87, 87, 90. Since there are 22 values, an even number, we find the arithmetic mean of the middle two: 81 and 82, to get the median. The median is 81.5.

3. Put the values in numerical order: 86, 89, 91, 91, 92, 92, 92, 92, 92, 93, 93, 93, 93, 94, 94, 94, 95, 95, 97, 100. There are 20 numbers, an even count, so we average the middle two, which are both 93. The median is 93.

4. Put the values in numerical order: 263, 268, 269, 269, 269, 272, 274, 275, 275, 275, 276, 276, 277, 278, 278, 279, 280, 281, 281, 281, 283, 285, 285. There are 23 numbers, an odd count, so we just take the middle value. The median is 276.

#### Practice

Find the median value for each set in questions 1 – 11.

1. $\{326, 314, 325, 315, 315, 307, 318, 318, 320, 322, 325, 321, 322, 320, 312, 325, 326, 325 \}$
2. $\{35, 37, 30, 42, 32, 42, 30, 45, 34, 43, 37, 43, 27, 41, 27, 45, 31, 44, 28, 45 \}$
3. $\{123, 167, 150, 132, 152, 128, 129, 160, 140, 121 \}$
4. $\{2120, 3040, 2180, 1892, 923, 9231, 8231 \}$
5. $\{1, 23, 41, 23, 61, 130, 210, 109, 592, 203, 12 \}$
6. $\{23.43, 32.52, 23.92, 32.25, 23.43, 29.55, 28.30, 31.54 \}$
7. $\left \{ \frac{1}{2}, \frac{4}{9}, \frac{3}{7}, \frac{2}{5}, \frac{21}{23}, \frac{16}{27}, \frac{3}{4} \right \}$
8. $\left \{.57, \frac{23}{100}, .05, \frac{17}{100}, \frac{52}{100}, .42, .44, \frac{45}{100} \right \}$
9. $\{12, 1.2, .12, 102, 120, .012, .120, 1202 \}$
10. $\left \{123, 12.3, \frac{12}{30}, \frac{123}{120}, \frac{120}{123}, \frac{30}{12}, \frac{1}{123}, 1.23, .123 \right \}$
11. . .

$\begin{array}{c|c c c c c c c c c c c c c c c c c c c} 2 &2 & 2 \\3&3&5&5&6&9&9&9 \\4&1&2&2&3&3&4&4&8\\5&2&4&5&5&7&7&7\end{array}$