Chapter 5 Glosary

Greedy Algorithm: Used in optimization problems. Tries to approximate the overall optimal way to solve a problem by making step-wise optimal choices.

Canonical Form: Normal, standard way of describing a mathematical object.

Latent Variable: Variable that is inferred from other variables. Not directly observed.

Parameteric Model: A statistical model that has all it’s information represented in its parameters. Those are the only thing needed to predict future or unknown values.

Oracle Property: An oracle knows the truth: it knows the true subset and is willing to act on it. The oracle property is that the asymptotic distribution of the estimator is the same as the asymptotic distribution of the MLE on only the true support. That is, the estimator adapts to knowing the true support without paying a price (in terms of the asymptotic distribution.)

NP-hardness: Problems that have non-deterministic polynomial time complexity. I.e. Subset Sum Problem.

Frobenius Norm: The norm of a matrix calculated under the root of the sum of all squared values.

Trace: The sum of the matrix elements on the main diagonal. Notation: \(Tr(A)\).