Return to Answer

[EDIT: as OP confirm that they need the Frobenius norm, this should be a complete solution for that case]

Since that norm is orthogonally invariant, $$ \|A - A'\| = \|P^T(A-A')\| = \|P^TA - DP^TA\| = \|(I-D)P^TA\|, $$ so essentially the question becomes "you are allowed to zero out $n$ rows of $B= P^TA$; which choice leaves you with the minimum norm"? This looks like a simpler reformulation.

If the norm is the Frobenius norm, then the answer is dropping the $n$ rows with the largest norm; I suspect that the same holds also for the 2-norm, but this is not immediate and sometimes these kinds of problems have a different solution when one switches norm.

[EDIT: as OP confirm that they need the Frobenius norm, this should be a complete solution for that case]

Since that norm is orthogonally invariant, $$ \|A - A'\| = \|P^T(A-A')\| = \|P^TA - DP^TA\| = \|(I-D)P^TA\|, $$ so essentially the question becomes "you are allowed to zero out $n$ rows of $B= P^TA$; which choice leaves you with the minimum norm"? This looks like a simpler reformulation.

If the norm is the Frobenius norm, then the answer is choosing the $n$ rows with the largest norm; I suspect that the same holds also for the 2-norm, but this is not immediate and sometimes these kinds of problems have a different solution when one switches norm.

[EDIT: as OP confirm that they need the Frobenius norm, this should be a complete solution for that case]

Since that norm is orthogonally invariant, $$ \|A - A'\| = \|P^T(A-A')\| = \|DP^TA - P^TA\| = \|(I-D)P^TA\|, $$ so essentially the question becomes "you are allowed to zero out $n$ rows of $B= P^TA$; which choice gives you the largest 2-norm"? This looks like a simpler reformulation.

If the norm is the Frobenius norm, then the answer is dropping the $n$ rows with the largest norm; I suspect that the same holds also for the 2-norm, but this is not immediate and sometimes these kinds of problems have a different solution when one switches norm.

[EDIT: as OP confirm that they need the Frobenius norm, this should be a complete solution for that case]

Since that norm is orthogonally invariant, $$ \|A - A'\| = \|P^T(A-A')\| = \|P^TA - DP^TA\| = \|(I-D)P^TA\|, $$ so essentially the question becomes "you are allowed to zero out $n$ rows of $B= P^TA$; which choice leaves you with the minimum norm"? This looks like a simpler reformulation.

If the norm is the Frobenius norm, then the answer is dropping the $n$ rows with the largest norm; I suspect that the same holds also for the 2-norm, but this is not immediate and sometimes these kinds of problems have a different solution when one switches norm.

Just a long comment.

I assume the norm is the operator norm (induced by the Euclidean 2-norm). Then it is orthogonally invariant and $$ \|A - A'\| = \|P^T(A-A')\| = \|DP^TA - P^TA\|, $$ so essentially the question becomes "you are allowed to keep $n$ rows of $B= P^TA$; which choice gives you the largest 2-norm"? This looks like a simpler reformulation.

If the norm were the Frobenius norm, then clearly the answer would be keeping the $n$ rows with the largest norm; I suspect that the same holds also for the 2-norm, but this is not immediate and sometimes these kinds of problems have a different solution when one switches norm.

[EDIT: as OP confirm that they need the Frobenius norm, this should be a complete solution for that case]

Since that norm is orthogonally invariant, $$ \|A - A'\| = \|P^T(A-A')\| = \|DP^TA - P^TA\| = \|(I-D)P^TA\|, $$ so essentially the question becomes "you are allowed to zero out $n$ rows of $B= P^TA$; which choice gives you the largest 2-norm"? This looks like a simpler reformulation.

If the norm is the Frobenius norm, then the answer is dropping the $n$ rows with the largest norm; I suspect that the same holds also for the 2-norm, but this is not immediate and sometimes these kinds of problems have a different solution when one switches norm.