I've been studying a paper where the authors employ the ADMM in a way that has left me somewhat perplexed. The paper focuses on addressing a robust principal component analysis (RPCA) problem, enhanced with an additional prior. This problem is formulated as: $$\underset{L,E}{\min} f_1(L) + f_2(L) + g(E) \quad \text{s.t.} \quad X = L + E$$

To maintain focus on the central query, I've simplified the problem to avoid any unnecessary details. In this equation, $X$ represents a constant matrix. All functions are convex.

To separate the variables in the objective function, the authors introduced auxiliary variables $Z$ and $Y$, reformulating the problem as: $$\underset{Z,E,Y}{\min} f_1(Z) + f_2(Y) + g(E) \quad \text{s.t.} \quad X = L + E, Z = L, Y = L$$

Subsequently, they presented the augmented Lagrange function as follows: $$ \begin{aligned} L(Z,E,Y,\Lambda_1,\Lambda_2, \Lambda_3) &= f_1(Z) + f_2(Y) + g(E) \\ &+ \langle L+E-X, \Lambda_1 \rangle + \lambda_1 \| L+E-X \| \\ &+ \langle Y - L, \Lambda_2 \rangle + \lambda_2 \| Y - L \| \\ &+ \langle Z - L, \Lambda_3 \rangle + \lambda_3 \| Z - L \|. \end{aligned} $$ The paper details an iterative approach to solve the subproblems for $Z$, $Y$, $L$, $E$, followed by updating the dual variables.

However, a point of confusion arises here. While $Z$ and $Y$ appear to be decoupled, $Z$-$L$ and $Y$-$L$ remain coupled. In other words, the variables are "latently coupled". The authors assert that since $Z$ and $Y$ are decoupled, it's feasible to iteratively solve for $Z$, $Y$, and then address the $L$-subproblem (which is quite easy as what remains about $L$ are norms and inner products). My problems are:

  1. Is their solution reasonable, or does it lean more towards a heuristic approach?
  2. Could there be a more efficient method to tackle this problem?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.