- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies the maximization of nonnegative weighted sums of pairwise inner products, where unknown vectors lie close to a common rank-two subspace. In particular, the objective is , where and . Each vector satisfies and , where projects onto the rank-two subspace . The paper shows that this problem can be solved in polynomial time with additive approximation using minimum cut. The paper also shows that the first-order change in the optimal value can be computed efficiently, while computing the second-order term is NP-hard. Moreover, exact optimization remains NP-hard even for a fixed positive . Finally, the paper extends the algorithm to a certified disclosure problem.
Critical strengths
- For the optimization problem considered in this paper, the authors provide a comprehensive theoretical analysis. They give a polynomial-time algorithm with an additive approximation guarantee and also prove NP-hardness results for exact optimization. These results provide a clear understanding of the computational tractability and hardness of the problem.
Critical weaknesses
- The paper does not provide a detailed motivation for the problem it studies. In particular, the proposed model seems rather restrictive, as it assumes that all unknown vectors lie close to a common rank-two subspace. It would be helpful if the authors could provide concrete examples and discuss when such assumptions are reasonable.
- The presentation of this paper is difficult to follow and can be improved significantly, especially in the abstract and introduction. Many technical concepts are introduced without sufficient intuition, making it difficult to understand the model considered in this paper, the main ideas, and the contributions. I suggest the authors improve the presentation by explaining the problem setting and the main results more clearly.
Questions for authors
See the above question