If so, and there's also a vacuum leak then increasing the revs might be enough to provide some more assistance, thus causing the pedal to sink slightly.
I would also concur with what HDI says about there being a bit of a leak somewhere. I have not noticed this in my car. I have noticed the brake pedal frees up when the engine starts but this is fairly normal.