Hypertext Maths Dictionary
Index
Adjoint
Basis of a space
Bayes'' Theorem
Conditional Probability
Constrained Optimisation
Correlation
Covariance
DES Cryptography
Dynamic Programming
Eigenvalue
Eigenvector
Eigenvector transform
Gradient
Hermitian
Hessian
Hidden Markov Model
Inner Product
Hotelling transform
Joint Probability
Kalman Filter
Karhunen-Loeve transform
Lagrange Multipliers
Laplacian
Linear Programming or Linear Optimisation
Linear Regression
Orthogonal
Positive definite
Principle component transform
Restricted normal form
RSA public key cryptography
Simplex method of Linear Optimisation
Singular
Singular Values
Standard Deviation
Singular Value Decomposition (SVD)
Taylors Series
Unitary Matrix
Variance
Adjoint
The transpose of the complex conjugate of a matrix. Often called Hermitian
Conjugate.
Return to index
Basis of a space
A basis of a space is a set of vectors that can generate any point in the space
by linear combination. The vectors may be linearly independent, such as the
x,y,z axes of 3D Cartesian space, but don''t have to be.
The smallest set of basis vectors is called a minimal spanning set, and they are
linearly independent, and therefore orthogonal.
Return to index
Bayes'' Theorem
The conditional probability
P(B|A)=P(A|B)P(B)/P(A)
Return to index
Conditional Probability
The probability of event A given event B is expressed as P(A|B) and can be
calculated from:
P(A|B)=P(A & B)/P(B)
where P(B) is the probability of event B and P(A&B) is the joint probability of
A and B.
Return to index
Constrained Optimisation
Optimisation is the process of minimising or maximising a function. Constrained
optimisation is optimisation subject to constraints on the functional parameters
or value.
eg: find the maximum of y=x^2+3 for x1
see Linear Programming and Lagrange Multipliers
Return to index
Correlation
The extent of the correspondence between two random variables. Can be calculated
by
cor(x,y)=cov(x,y)/sqrt(vx x vy)
where cor(x,y) is the correlation between x and y, cov(x,y) is the covariance of
x and y and vx, vy are the variances of x and y.
If x and y are uncorrelated, then they are independent. They are positively
correlated if x increases as y does and negatively correlated if x decreases as
y increases.
The correlation matrix Ca of vector A of length n is the n x n matrix the
entries of which are the pairwise correlations of the elements of A. The i,jth
element of Ca is the correlation of the ith and jth elements of A.
Return to index
Covariance
Is a measure of the association between two random variables, X and Y.
Is calculated as the expected value of the product of their deviations from
their means.
cov(X,Y)=E((X-Mx)(Y-My)) (=E(XY)-MxMy =0 if X,Y are independent)
Mx= E(X) is the mean of X
A covariance matrix is a matrix, the entries of which are the covariances of the
pairs of variables in a set.
e.g. if a set of variables is defined as {x,y,z} and the covariances are
respectively cov(x,y) cov(x,z) cov(y,z) then the covariance matrix is:
- |cov(x,x) cov(x,y) cov(x,z)|
|cov(x,y) cov(y,y) cov(y,z)|
|cov(x,z) cov(y,z) cov(z,z)|
-
Note that cov(y,x)=cov(x,y) so the covariance matrix is symmetric.
Also, cov(x,x)=E((X-Mx)^2)=variance(x)
See Correlation
Return to index
DES Cryptography
A ''secret key'' method of enciphering a message.
DES is the Data Encryption Standard, an encryption block cipher defined and
endorsed by the U.S. government in 1977 as an official standard; the details can
be found in the latest official FIPS (Federal Information Processing Standards)
publication concerning DES [NIS93b]. It was originally developed at IBM. DES has
been extensively studied since its publication and is the most well-known and
widely used cryptosystem in the world.
DES is a symmetric cryptosystem: when used for communication, both sender and
receiver must know the same secret key, which is used both to encrypt and
decrypt the message. DES can also be used for single-user encryption, such as to
store files on a hard disk in encrypted form. In a multi-user environment,
secure key distribution may be difficult; public-key cryptography provides an
ideal solution to this problem (see RSA Cryptography).
DES has a 64-bit block size and uses a 56-bit key during encryption. It is a
16-round Feistel cipher and was originally designed for implementation in
hardware.
The algorithm is as follows:
Feistel ciphers are a special class of iterated block ciphers where the
ciphertext is calculated from the plaintext by repeated application of the same
transformation or round function.
In a Feistel cipher the text being encrypted is split into two halves (32 bits
each for DES). The round function f is applied to one half using a subkey
(derived from the 56 bit secret key) and the output of f is exclusive-ored with
the other half. The two halves are then swapped. For DES, the function f is a
''permutation'' operation where the bits of the block to be coded are shuffled
according to the value of the subkey. Each round follows the same pattern except
for the last round where there is no swap. For DES, there are 16 rounds
(iterations).
Decoding is the same as encoding, using the same key, which is why this is
called a symmetric encryption process.
[Fei73] H. Feistel. Cryptography and Computer Privacy, Scientific American, May
1973.
Return to index
Dynamic Programming
Based on Bellman''s principle, is a method to produce the optimal solution for an
n step process based on the optimal solution to an n-1 step process, which
commences with the optimal solution of the first step. (Compare this to proof by
induction?) (BTW, Bellman''s principle of optimality should not be confused with
Lewis Carrol''s Bellmans principle, "What is said thrice is true." There does
however seem to be some similarity. :-) )
Return to index
Eigenvector
An eigenvector of a matrix A is a vector e such that eA=Le where L is a scalar.
L is known as an eigenvalue of A corresponding to the eigenvector e.
Return to index
Gradient
The gradient of a scalar field is a vector field of the first derivatives of the
scalar function along each axis. eg
Where i and j denote the unit vectors along the x and y axes.
Return to index
Hermitian
A matrix is hermitian if it is equal to its conjugate transpose. For a real
matrix, this means if and only if (iff) it is symmetric
Return to index
Hessian
A Hessian matrix H of a function is the matrix of its second differentials
evaluated at a point, giving a measure of the curvature at that point.
At a minimum of the function, H is positive definite and at a maximum, negative
definite. It is indeterminate at a saddle.
If the function is of quadratic form,
f(x)=x''Hx+b''x+c
then the Hessian can be used to map differences in position into differences in
gradient.
If g1 and g2 are the gradients at x1 and x2 respectively, then
g2-g1=H(x2-x1).
Return to index
Inner Product
The inner product of two vectors is their product in a given inner product
space.
In particular in Euclidean space it is the scalar that results from the sum of
the products of the components of the vector for each axis. e.g.
if A=ax+by+cz
and B=dx+ey+fz
then their inner product
C=A.B=ad+be+cf
A.B can also be calculated as |A||B|cos(g) where g is the angle between the
vectors A and B
(Bold, such as A refers to vector, and x,y and z are the unit cartesian axes for
3d space)
Return to index
Hidden Markov Model
A hidden Markov model is a stochastic automaton consisting of a set of states qi
each with an associated conditional probability distribution p(xn|qi) for an
output vector xn, and transition probabilities P(qj|qi) for transitions between
states. It is called hidden because the states are not seen, only the output
vectors.
Return to index
Joint Probability
The probability of event A and event B is expressed as P(A&B).
For independant variables, P(A&B)=P(A)P(B).
eg for a two-up toss, the prob of a head and a tail is 1/2*1/2
P(A&B) is also known as the prob of A ''intersection'' B, from the Venn diagram
showing the classes in sample space where B is the event ''at least one tail'' and
A is the event ''at least one head''. The intersection of the two classes is the
subclass, ''a head and a tail''.
Return to index
Kalman Filter
A Dynamic Programming method that produces ...
|
|
|
|
|
|
|
|
|
Go to the beginning of the document
Go to previous page
Go to next page
Go to the end of document
