IIT M IMPROVEMENT AN EXAM QDD3 22 - 22 Dec 2024

Concepts this paper tests

Auto-generated summary from the source site. Handy as a checklist; the lessons above explain each idea from scratch.

Here’s a structured summary of core topics, concepts, principles, and equations essential for the exam, followed by Mermaid knowledge graphs to visualize relationships.

---

Core Topics & Key Concepts

1. Linear Algebra & Matrix Theory

Key Concepts:

• Quadratic Forms & Matrices:

  • A quadratic form is given by $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x}$, where $A$ is symmetric.
  • For $f(x_1, x_2, x_3) = x_1^2 + 2x_1x_2 + 5x_2^2 + 3x_3^2$, the matrix $A$ is:

• Properties of $A$:

  • Positive Definite: $\mathbf{x}^T A \mathbf{x} > 0$ for all $\mathbf{x} \neq 0$.
  • Singularity: $A$ is non-singular if $\det(A) \neq 0$.
  • Symmetric: $A = A^T$.

• Eigenvalues & Eigenvectors:

  • If $\det(A) = 0$, then $0$ is an eigenvalue.
  • Non-zero eigenvalues of $A^T A$ and $A A^T$ are identical.
  • Nullity: If $\det(A) \neq 0$, nullity is $0$ (no non-trivial solutions to $A\mathbf{x} = 0$).
  • Rank: If all eigenvalues are non-zero, $\text{rank}(A) = n$.

• Special Matrices:

  • Unitary Matrix: $A^* A = I$ (columns are orthonormal).
  • Hermitian Matrix: $A = A^*$ (self-adjoint).
  • Eigenvalues of Hermitian matrices are real.
  • Eigenvectors of unitary matrices are orthogonal.

Key Equations:

1. Quadratic Form Expansion:

1. Eigenvalue Equation:

1. Determinant & Rank:

---

2. Convex Optimization

Key Concepts:

• Convex Sets:

  • A set $S$ is convex if for any $a, b \in S$, $\theta a + (1-\theta)b \in S$ for $\theta \in [0,1]$.
  • Examples: Midpoint ($\theta = 0.5$), weighted averages (e.g., $0.4a + 0.6b$).

• Convex Functions:

  • $f$ is convex if:

• Examples:

  • $f(x) = e^x$ (convex).
  • $f(x) = x \ln x$ (convex for $x > 0$).
  • $f(x, y) = e^{x+y}$ (convex).
  • Composition $f \circ g$ may preserve convexity under certain conditions.

• KKT Conditions (Karush-Kuhn-Tucker):

  • Necessary for optimality in constrained optimization.
  • For a problem:

The KKT conditions are:

Key Equations:

1. Convex Combination:

1. KKT Lagrangian:

1. Gradient Condition:

---

3. Probability & Statistics

Key Concepts:

• Random Variables & Distributions:

  • Uniform Distribution: $X \sim \text{Uniform}(0,1)$, PDF $f(x) = 1$ for $x \in [0,1]$.
  • Normal Distribution: $X \sim N(\mu, \sigma^2)$, PDF:

• Linear Combinations of Normals: If $X \sim N(\mu_1, \sigma_1^2)$, $Y \sim N(\mu_2, \sigma_2^2)$, then:

• Joint & Marginal Distributions:

  • For joint PDF $f_{X,Y}(x,y)$, the marginal PDF of $X$ is:

• Transformation of Variables: For $U = X + Y$, $V = X - Y$, the joint PDF $f_{U,V}(u,v)$ is derived using the Jacobian.

• CDF of Min/Max:

  • For independent $X, Y \sim \text{Uniform}(0,1)$, the CDF of $Z = \min(X, Y)$ is:

Key Equations:

1. CDF of Minimum:

1. Linear Combination of Normals:

1. Joint PDF Transformation:

where $J$ is the Jacobian determinant.

---

4. Optimization Algorithms

Key Concepts:

• Gradient Descent:

  • Update rule:

• Learning Rate ($\eta$): Controls step size.
• Example: For $f(x,y) = x^2 + y^2 -6x -8y$, the gradient is:

Starting at $(1, 2)$ with $\eta = 0.2$:

Then $20x + 20y = 20(1.8) + 20(2.8) = 92$.

Key Equations:

1. Gradient Descent Update:

1. Gradient of Quadratic Function:

---

2. Convex Optimization

3. Probability & Statistics

4. Optimization Algorithms

---

Exam Preparation Checklist

1. Linear Algebra:

   • Know how to construct $A$ from a quadratic form.
   • Understand positive definiteness, eigenvalues, and singularity.
   • Recall properties of unitary/Hermitian matrices.

1. Convex Optimization:

   • Master KKT conditions and convex set/function definitions.
   • Practice deriving Lagrangians for constrained problems.

1. Probability:

   • Be fluent in CDF/PDF transformations (e.g., min/max of uniforms).
   • Memorize linear combination rules for normal distributions.

1. Optimization Algorithms:

   • Implement gradient descent updates manually for simple functions.

1. Key Equations to Memorize:

   • Quadratic form matrix $A$.
   • KKT Lagrangian and gradient conditions.
   • CDF of $\min(X, Y)$ for uniform RVs.
   • Gradient descent update rule.