The　weighted　low-rank　approximation　problem　is　a　fundamental　numerical　linear　algebra　problem　and　has　many　applications　in　machine　learning.　Given　a　n　×　n　weight　matrix　W　and　a　n　×　n　matrix　A,　the　goal　is　to　find　two　low-rank　matrices　U,　V　∊　n×k　such　that　the　cost　of　W　◦　(UV　Τ　-　A)2F　is　minimized.　Previous　work　has　to　pay　Ω(n2)　time　when　matrices　A　and　W　are　dense,　e.g.,　having　Ω(n2)　non-zero　entries.　In　this　work,　we　show　that　there　is　a　certain　regime,　even　if　A　and　W　are　dense,　we　can　still　hope　to　solve　the　weighted　low-rank　approximation　problem　in　almost　linear　n1+o(1)　time.　Copyright　2025　by　the　author(s).