Binary Hypothesis Testing
- The goal is to determine which of two distributions generated an observed sample.
- A randomized detector is introduced as a policy for attributing observations to distributions.
- Scalarizing the problem simplifies the solution.
- Minimizing the total number of errors leads to a simple solution based on maximum likelihood.
- Minimizing the maximum of false positive and false negative errors results in a non-deterministic detector.
Experiment Design
- The concept of experiment design involves linear measurements and a measurement vector.
- The measurements are normalized to have the same standard deviation.
- The goal is to choose the best subset of experiments to obtain the best estimate of a parameter.
- The optimality criterion is based on the size of the confidence ellipsoid.
- A simple experiment design method is to choose the experiment with the highest signal-to-noise ratio.
- The Gaussian model allows for the experiment design problem to be formulated as an integer programming problem.
- A relaxation technique for solving experiment design problems is introduced.
- The speaker suggests using a probabilistic approach to determine which experiment to perform.
- The rounded solution may not minimize the confidence ellipsoid volume but is close to the optimal solution.
- The assumption of M (the number of experiments) being much larger than P (the number of options) is made.
- The speaker introduces the concept of D-optimal experiment design.
Optimization Problems Involving Polyhedra and Ellipsoids
- The goal is to find the minimum volume ellipsoid that covers the given experiments.
- The experiments with higher signal-to-noise ratio (SNR) are more desirable and should be chosen.
- The optimal experiment design chooses two experiments that are closest to orthogonal to each other.
- Adding a budget constraint allows for cost-effective experiment design.
- Complex constraints can be incorporated into the convex optimization problem.
- The volume of the ellipsoid is inversely proportional to the square root of the determinant of W.
- Determining if two polyhedra intersect is a convex problem.
- Finding the minimum distance between two polyhedra is a convex optimization problem.
Minimum Volume Ellipsoid
- This can be formulated as a convex optimization problem.
- One application is in outlier detection.
- A method called "ellipsoidal peeling" can be used to iteratively remove outliers and find the minimum volume ellipsoid.
- Finding the minimum volume ellipsoid that covers a polyhedron given an inequality form is NP-hard.
- The dual problem of finding the maximum volume ellipsoid that fits inside a polyhedron is tractable if the polyhedron is described by inequalities but NP-hard if it's described by its vertices.
- The Löwner-John ellipsoid is the minimum volume ellipsoid that covers a convex bounded set with non-empty interior.
- Ellipsoids are universal approximators of convex sets within a factor of √n.
- Any norm on ℝ^n can be approximated with a quadratic norm with error no more than the fourth root of n.
