Stanford EE364A Convex Optimization I Stephen Boyd I 2023 I Lecture 11

()

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.

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.

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.

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.