Upper bound for smallest eigenvalue of matrix ‖ ϕ ( x ) ‖ 2 ≤ 1I am reading a paper which claims the following. But I am not sure how to show it rigorously. Any help is appreciated.For all x ∈ X , assume the d-dimensional feature map is bounded such that ‖ ϕ ( x ) ‖ 2 ≤ 1. For any data distribution μ consider the matrix A = E x ∼ μ [ ϕ ( x ) ϕ ( x ) ⊤ ]Prove that the largest possible minimum eigenvalue σ min min of matrix A satisfies σ min ( A ) ≤ 1 d

Question

Upper bound for smallest eigenvalue of matrix   ‖  ϕ  (  x  )      ‖    2    ≤  1I am reading a paper which claims the following. But I am not sure how to show it rigorously. Any help is appreciated.For all   x  ∈      X  , assume the d-dimensional feature map is bounded such that   ‖  ϕ  (  x  )      ‖    2    ≤  1. For any data distribution   μ consider the matrix  A  =            E              x      ∼      μ        [  ϕ  (  x  )  ϕ  (  x      )    ⊤    ]Prove that the largest possible minimum eigenvalue       σ          min       min of matrix A satisfies      σ          min        (  A  )  ≤      1    d

eurgylchnj · Accepted Answer

Since A is a   d  ×  d positive semidefinite matrix, its eigenvalues are nonnegative and they coincide with the singular values of A. Therefore                              σ          min                (        A        )        =                  λ          min                (        A        )                            ≤                  1          d                          ∑                      i            =            1                    d                          λ          i                (        A        )        =                  1          d                tr        ⁡        (        A        )                                          =                  1          d                tr        ⁡                  (                      E                                (            ϕ                          ϕ              ⊤                        )                    )                =                  1          d                          E                          (          tr          ⁡          (          ϕ                      ϕ            ⊤                    )          )                                                  =                  1          d                          E                          (          ‖          ϕ                      ‖            2            2                    )                ≤                  1          d                          E                (        1        )        =                  1          d                .